遞歸的代碼是以前數(shù)據(jù)結(jié)構(gòu)書上常見的：

    public ArrayList<Integer> inorderTraversal(ConstructBinaryTreefromPostorderandInorderTraversal.TreeNode root) {
        ArrayList<Integer> res = new ArrayList<>();
        dfs(res, root);
        return res;
    }

    private void dfs(List<Integer> res, ConstructBinaryTreefromPostorderandInorderTraversal.TreeNode node) {
        if (node == null) return;
        dfs(res, node.left);
        res.add(node.val);
        dfs(res, node.right);
    }

非遞歸用stack模擬中序遍歷，要理解啊，不能死記硬背。注意while條件和while里面的if。

public class Solution {
        public ArrayList<Integer> inorderTraversal(TreeNode root) {
            ArrayList<Integer> res = new ArrayList<>();
            LinkedList<TreeNode> stack = new LinkedList<>();
            //注意while條件是或
            while (root != null || !stack.isEmpty()){
                if (root!=null){
                    stack.push(root);
                    root = root.left;
                }else {
                    root = stack.pop();
                    res.add(root.val);
                    root = root.right;
                }
            }
            return res;
        }
}

MAR 25TH
這題今天做98. Validate Binary Search Tree 的時候又來復習了一遍，又忘的差不多了。。記得當時還在考慮為什么while里面要用||而不是&&。

這題還可以這樣寫：

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> list = new ArrayList<>();
    if(root == null) return list;
    Stack<TreeNode> stack = new Stack<>();
    while(root != null || !stack.empty()){
        while(root != null){
            stack.push(root);
            root = root.left;
        }
        root = stack.pop();
        list.add(root.val);
        root = root.right;
        
    }
    return list;
}

JULY 29 REVIEW

又看了一遍迭代的方法，仍然寫不出。。上面那個代碼，兩個while循環(huán)其實挺清晰的，但是root = root.right那邊還是挺難想到的。還有就是外層的while，兩種情況；1是root!= null的情況，這種比較好考慮，就是首次進入的時候；2是root==null的情況，statck不為空，這種就是dfs到棧最底的情況。