給定一個(gè)二叉樹，返回它的中序 遍歷。

示例:

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

輸出: [1,3,2]

中序遍歷的話比較簡(jiǎn)單,代碼如下:

 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);
        }
    }

題目建議用迭代的方式來(lái)處理,其實(shí)就是模擬遞歸中序遍歷的過(guò)程,這里就需要講下中序遍歷的過(guò)程:

假如說(shuō),現(xiàn)在有這樣的一顆二叉樹:

      5      
    /   \    
   3    6    
  / \    \   
 2  4     8  

它的中序遍歷過(guò)程是怎么樣的呢,首先每個(gè)節(jié)點(diǎn)在遍歷的過(guò)程中會(huì)訪問(wèn)三次,如果在第一次訪問(wèn)輸出就是前序,如果第二次訪問(wèn)則是中序,如果第三次訪問(wèn)則是后續(xù).中序訪問(wèn)如下,第一次訪問(wèn)5,不輸出,接著訪問(wèn)3,不輸出,訪問(wèn)2,2第一次訪問(wèn)不輸出,判斷左子節(jié)點(diǎn)為null,此時(shí)返回到2這個(gè)節(jié)點(diǎn),此時(shí)輸出2,訪問(wèn)完2后,返回到3,此時(shí)輸出3,接著訪問(wèn)4,第一次不輸出,第二次輸出4,在接著返回到3,然后返回到5,訪問(wèn)5,接著訪問(wèn)6.....整個(gè)過(guò)程大概是這樣子5->3->2->2->2->3->4->4->4->3->5->6->6->8->8->8->6->5,所以模擬的過(guò)程如下:

  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的左子節(jié)點(diǎn)全部入棧
            while (cur.left != null){
                cur = cur.left;
                stack.add(cur);
            }
            //彈出左左邊的元素
            TreeNode pop = stack.pop();
            list.add(pop.val);
            //如果右子節(jié)點(diǎn)不為空,此時(shí)入棧
            if (pop.right != null){
                cur = pop.right;
                stack.add(cur);
            }
        }
        return list;
    }