逸如风的个人博客

Morris遍历

Morris遍历：

优点：不同于我们之前递归遍历或者借助栈来进行树的遍历，因为Morris遍历可以在保证时间复杂度依然为O(N)的情况下可以将空间复杂度降低为O(1)

假设当前节点为cur,最一开始来到树根，什么时候停呢，当cur来到nil的时候就停止

如果当前节点没有左子树，直接向右移动
如果当前节点有左子树，找到当前节点左子树的最右节点mostRight
1. 如果mostRight的右指针指向null，那么mostRight.Right=Cur,cur=cur.Left
2. 如果mostRight的右指针指向cur，那么mostRight.Right=nil,cur=cur.Right

遍历之后发现一个问题：任何一个节点，只要有左孩子Morris遍历的时候会遍历两次，也就是有左树的节点，左树不为空，首先遍历当前节点，然后遍历左树，遍历之后再回到当前节点，所以当前节点会遍历两次。因为用这个就可以知道是第一次来到自己还是第二次来到自己。

Morris先序遍历：

第一次遍历到该节点的时候直接打印（没有左子树的节点会遍历到一次，有左子树的节点会遍历到两次，但是我们第一次就应该打印）

Morris先序遍历代码

func MorrisPreOrderTraverse(root *TreeNode) []int {
	if root == nil {
		return nil
	}

	var mostRight *TreeNode
	cur := root
	var ret []int
	for cur != nil {
		//如果当前节点没有左子树
		if cur.Left == nil { //当前节点向右移动  (只有没有左子树的节点会走这一步)
			ret = append(ret, cur.Val)
			cur = cur.Right
		} else { //找到当前节点左子树的最右节点
			mostRight = cur.Left

			for mostRight.Right != nil && mostRight.Right != cur {
				mostRight = mostRight.Right
			}
			//此时mostRight就是当前节点左子树的最右节点
			if mostRight.Right == nil { //说明是第一次来到
				ret = append(ret, cur.Val)
				mostRight.Right, cur = cur, cur.Left
			} else { //说明是第二次来到(只有有左子树的时候才会有第二次来到)
				mostRight.Right, cur = nil, cur.Right
			}
		}
	}

	return ret
}

2021-11-27 算法