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