Morris遍历:
优点:不同于我们之前递归遍历或者借助栈来进行树的遍历,因为Morris遍历可以在保证时间复杂度依然为O(N)的情况下可以将空间复杂度降低为O(1)
假设当前节点为cur,最一开始来到树根,什么时候停呢,当cur来到nil的时候就停止
- 如果当前节点没有左子树,直接向右移动
- 如果当前节点有左子树,找到当前节点左子树的最右节点mostRight
- 如果mostRight的右指针指向null,那么mostRight.Right=Cur,cur=cur.Left
- 如果mostRight的右指针指向cur,那么mostRight.Right=nil,cur=cur.Right
遍历之后发现一个问题:任何一个节点,只要有左孩子Morris遍历的时候会遍历两次,也就是有左树的节点,左树不为空,首先遍历当前节点,然后遍历左树,遍历之后再回到当前节点,所以当前节点会遍历两次。因为用这个就可以知道是第一次来到自己还是第二次来到自己。
Morris先序遍历:
第一次遍历到该节点的时候直接打印(没有左子树的节点会遍历到一次,有左子树的节点会遍历到两次,但是我们第一次就应该打印)
Morris先序遍历代码
1 | func MorrisPreOrderTraverse(root *TreeNode) []int { |