[数据结构与算法]二叉树的莫里斯遍历

一、中序遍历

1.1 算法思路

中序遍历要求每个结点被遍历一次，最优时间复杂度为O(n)，递归和迭代都需要记录中间状态。

注意观察需要改变指向的节点的共同特点
? E是A的左子树的中序遍历最后一个点（可以理解为最近的前继节点）
? D是B的中序遍历最后一个点（可以理解为最近的前继节点）

1.2 算法描述

假设当前遍历至结点x：

1. 如果x没有左子树，将其加入目标序列，再遍历右子树，x=x.right
2. 如果x有左子树，找到左子树上中序遍历最后一个结点（记作ex-point）
   ? 如果ex-point的右子树为空，则将其指向x，访问x的左子树，x=x.left
   ? 如果ex-point右子树不为空，此时其右子树已经指向x，说明左子树已经遍历完成，将ex-point右子树置空，将x加入目标序列，然后访问x的右子树,x=x.right

1.3 代码实现

 public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res=new ArrayList<>();
        TreeNode exPoint =null;

        while(root!=null){
            //step1 找到左子树中序遍历最后一个节点
            if(root.left!=null){
               exPoint=root.left;
               //exPoint.right!=root 判断是否已经改变指向
               while(exPoint.right!=null && exPoint.right!=root){
                   exPoint=exPoint.right;
               }

               if(exPoint.right == null){
                   //将exPoint指向root，建立关系，进行左遍历
                   exPoint.right=root;
                   root=root.left;
               }else{
                    //遍历完毕，断开连接，进行右遍历
                   res.add(root.val);
                   exPoint.right=null;
                   root=root.right;
               }
            }else{
                res.add(root.val);
                root=root.right;
            }
        }
        return res;
    }