莫里斯遍历 有关二叉树的遍历算法 非递归,无额外空间,时间复杂度O(n) 空间复杂度O(1) 很巧妙的遍历算法 核心思想就是利用树节点中的空指针 考虑非递归算法,如果我们不用栈的话,最主要的问题就是遍历完一个节点的左子树后怎么回到这个节点并遍历他的右子树 在遍历左子树的时候,最后一个遍历的节点一定是二叉树中序遍历中,当前节点的前一个节点 也就是当前节点左子树的最右边的节点 我们可以把这个前驱节点的右子树设为当前节点,这样遍历完左子树的时候,也就是遍历完这个前驱节点的时候,我们可以通过先前设置的那个指针回到当前节点,…