ORID24

145 Binary Tree Postoder traversal

这道题如果用recursion会很方便，但可能会follow up用iterative的方式去解决这道题
如果要用iterative，核心思想就是用Stack， tree traversal 一共有三种形式，inorder, preorder, postorder
inorder 是（left root right）说白了就是先看他左边的，然后看自己，然后看右边的。preorder（root, left, right），这说白了就是一定要先看自己，然后左，最后右。postorder 是left, right, root

94 Binary Tree Inorder Traversal

典型的inorder traversal, 也就是left, root, right
这道题我用iterative的方法来解决，通过stack 来实现。主要思想如下

1. 从root一直走到最左边的Leaf node, 因为你要从左边开始
2. 在这个过程中，每个node都要存到stack上面，因为之后你要通过stack来把他们的值取出来。
3. 走到最左边之后，把它的值从stack取出来，然后存到results里，之后在pop，然后在取当前stack的值root = stack.pop()，然后current node = root.right
4. 继续循环。

    public List<Integer> inorderTraversal(TreeNode root) {
        //inorder is left, root, right use recursion
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> result = new ArrayList<>();
        TreeNode current = root;
        while (current != null || !stack.isEmpty()) {   //第一个while就是整个iteration的while loop
            while (current != null) {    // 第二个while是在不断的往最左边走
                stack.add(current);
                current = current.left;
            }
            current = stack.peek();
            stack.pop();
            result.add(current.val);
            current = current.right;   //这里直接等于current.right 是因为最左边的右边实际上是null, 但第一个while有个stack condition，
                                     //所以会直接循环到stack上面，然后把当前的stack的值存起来，也就是root.val，然后再往右走（确保把这个root的右边也放到result里面）
        }
        return result;



    }

144 preorder traversal

一样的道理，preorder 是 root, left, right， 所以用recursion实现很容易。思想如下：

1. 先记录当前root的值，results.add(root.val)
2. 然后用recursion来记录所有左边的值（results.addAll(preorderTraversal(root.left))）
3. 然后用同样的recursion记录右边的值（results.addAll(preorderTraversal(root.right))）
4. return result

public List<Integer> preorderTraversal(TreeNode root) {
        //recursion preorder is root, left, right
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        result.add(root.val);
        result.addAll(preorderTraversal(root.left));
        result.addAll(preorderTraversal(root.right));
        return result;
    }

可以看出来很简洁，如果要用iterative方式来实现，我们应该还是用stack来实现。

1. 记录当前的值，
2. 如果右边不是null, 把它加到stack里面（先加右边是因为你最后取值的时候是要先把左边的取出来，所以放的时候要先把右边的放进去。remember preorder is root, left, right. So when you put treenode into stack, put right hand side first.
3. 然后同样的方式，这次是左边
4. 循环

    public List<Integer> preorderTraversal(TreeNode root) {
        //iteration
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();

        if (root == null) {
            return result;
        }
        stack.add(root);
        while (!stack.isEmpty()) {
            TreeNode current = stack.pop();
            result.add(current.val);
            if (current.right != null) {
                stack.add(current.right); 
            }
            if (current.left != null) {
                stack.add(current.left);
            }
        }
        return result;
    }