P94

给定一个二叉树，返回它的中序 遍历。

示例:

输入: [1,null,2,3]
1
\
2
/
3

输出: [1,3,2]

中序遍历的话比较简单,代码如下:

 public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        inorderTraversal(root,list);
        return list;
    }

    private void inorderTraversal(TreeNode node, List<Integer> list) {
        if (node != null){
            inorderTraversal(node.left,list);
            list.add(node.val);
            inorderTraversal(node.right,list);
        }
    }

题目建议用迭代的方式来处理,其实就是模拟递归中序遍历的过程,这里就需要讲下中序遍历的过程:

假如说,现在有这样的一颗二叉树:

      5      
    /   \    
   3    6    
  / \    \   
 2  4     8  

它的中序遍历过程是怎么样的呢,首先每个节点在遍历的过程中会访问三次,如果在第一次访问输出就是前序,如果第二次访问则是中序,如果第三次访问则是后续.中序访问如下,第一次访问5,不输出,接着访问3,不输出,访问2,2第一次访问不输出,判断左子节点为null,此时返回到2这个节点,此时输出2,访问完2后,返回到3,此时输出3,接着访问4,第一次不输出,第二次输出4,在接着返回到3,然后返回到5,访问5,接着访问6.....整个过程大概是这样子5->3->2->2->2->3->4->4->4->3->5->6->6->8->8->8->6->5,所以模拟的过程如下:

  public List<Integer>  inorderTraversalNR(TreeNode root){
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        stack.add(root);
        TreeNode cur = root;
        while (!stack.isEmpty()&&cur!=null){
        //首先把root的左子节点全部入栈
            while (cur.left != null){
                cur = cur.left;
                stack.add(cur);
            }
            //弹出左左边的元素
            TreeNode pop = stack.pop();
            list.add(pop.val);
            //如果右子节点不为空,此时入栈
            if (pop.right != null){
                cur = pop.right;
                stack.add(cur);
            }
        }
        return list;
    }