94.二叉树中序遍历

1. 栈实现：要注意外层while循环跳出条件，要考虑到树只有右子树的情况。空间O(n)

     while(!stack.isEmpty()||curr!=null)//有左子树栈不为空或者只有右子树
        {
            while(curr!=null)
            {
                stack.push(curr);
                curr=curr.left;
            }
            curr=stack.pop();
            res.add(curr.val);
            curr=curr.right;
        }
   

2. 线索二叉树：比较复杂，假设curr为当前遍历到的节点，分几种情况:

   • 如果没有左孩子，那么访问当前节点，开始遍历右子树，curr=curr.right

   • 如果有左子树，那么在左子树中找到curr的前驱节点pre。

     （pre=curr.left; while(pre.right!=null&&pre.right!=curr) pre=pre.right;），这时候根据pre.right的情况(如果不分情况，只进行前驱节点指向curr操作，curr=curr.left，会导致后面curr的左子树访问完回到curr时，会继续访问左子树，无法判断左子树是处于还没进行访问，开始连接前驱节点的状态还是已经访问完毕的状态)由分为两种操作：

     • 若pre.right=null,则连接前驱，pre.right=curr;然后开始遍历左子树curr=curr.left。
     • 若pre.right=curr,则说明当前是已经访问完左子树，第二次回到curr节点的状态，这时候就访问当前节点curr，然后开始遍历右子树curr=curr.right。这里断不断开连接对后续操作没有影响。

   每个节点被访问两次，时间复杂度O(2n)=O(n)，空间复杂度O(1)。