Traversal

Preorder Traversal

114 Flatten Binary Tree to Linked List

Revised preorder traversal

这道题，乍一看好像很简单，直接pre-order traversal (curr -> L -> R)，然后按顺序依次转化成rootNode的右子树。这样的话，我们需要另一个数组存储我们的pre-order traversal，再依次粘贴到rootNode的右子树上。

我们可以用递归，从右子树开始扫起，进行 reverse preorder，即 R -> L -> curr。同时keep 一个 global 的 prev pointer, pointing to the last executed node. 每次我们需要对当前node进行，root.right = prev, root.left = null, prev = root

public void flatten(TreeNode root) {
    helper(root, null);
}
private TreeNode helper(TreeNode root, TreeNode pre) {
    if (root == null) return pre;
    pre = helper(root.right, pre);
    pre = helper(root.left, pre);
    root.right = pre;
    root.left = null;
    return root;
}

Inorder Traversal

94 Binary Tree Inorder Traversal

Iterative 方法 in order 遍历二叉树。借助 Stack 实现。

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    Deque<TreeNode> stack = new LinkedList<>();
    TreeNode cur = root;
    while(cur != null || !stack.isEmpty() ) {
        if (cur != null) {
            stack.offerLast(cur);
            cur = cur.left;
        } else {
            cur = stack.pollLast();
            res.add(cur.val);
            cur = cur.right;
        }
    }
    return res;
}

Postorder Traversal

145 Binary Tree Postorder Traversal

循环的方式后序遍历二叉树。记忆点：1.从上往下和从下往上的过程不太一样，需要分开讨论。2.从上往下的时候，需要先遍历左子树，再右子树，最后是节点。3.从下往上的时候，也有两种情况，第一种是从右子树上来或者左子树上来并且已无右子树可以遍历，第二种是从左子树上来并且还有右子树可以遍历。

Recursion Solution

Iterative Solution

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if (root == null) return res;
    Deque<TreeNode> stack = new LinkedList<>();
    stack.add(root);
    TreeNode pre = null;
    while (!stack.isEmpty()) {
        TreeNode cur = stack.peekFirst();
        // if we are going down, try to go left first
        if (pre == null || pre.left == cur || pre.right == cur) {
            if (cur.left != null) {
                stack.offerFirst(cur.left);
            } else if (cur.right != null) {
                stack.offerFirst(cur.right);
            } else {
                stack.pollFirst();
                res.add(cur.val);
            }
        } 
        // if we are going up from the right side or from left side but we can not go right afterwards
        else if (cur.right == pre || cur.left == pre && cur.right == null) {
            stack.pollFirst();
            res.add(cur.val);
        }
        // if we are going up from the left side and we can go down right side
        else {
            stack.offerFirst(cur.right);
        }
        pre = cur;
    }
    return res;
}