Tree Traversal

• 如果用Iterative的方式来Traversal的话，非常重要的对stack 和 Queue 的运用，应该非常熟悉的写出来
• 如果用DFS来做的话 Pre-Order, In-Order, Post-Order 都是很容易的用Recursive的方式
• 如果用BFS来做Level-Order 也是可以用两种方式来搞。

DFS Traversal

Pre-Order

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
      TreeNode cur = stack.pop();
      if (cur == null) continue;
      res.add(cur.val);
      stack.push(cur.right);  // right first
      stack.push(cur.left);   // left behind
    }
    return res;
  }

In-Order(BST 中的重中之重，顺序遍历)

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    Stack<TreeNode> stack = new Stack<>();
    leftPush(stack, root);
    while (!stack.isEmpty()) {
      TreeNode cur = stack.pop();
      res.add(cur.val);
      leftPush(stack, cur.right);
    }
    return res;
  }
private void leftPush(Stack<TreeNode> stack, TreeNode root) {
  while (root != null) {
    stack.push(root);
    root = root.left;
  }
}

Post-Order

public ArrayList<Integer> postorderTraversal(TreeNode root) { 
    ArrayList<Integer> result = new ArrayList<Integer>(); 
    Deque<TreeNode> stack = new ArrayDeque<TreeNode>(); 
    TreeNode prev = null; // previously traversed node 
    TreeNode curr = root; 
    if (root == null)  return result;  
    stack.push(root);

    while (!stack.empty()) { 
        curr = stack.peek(); 
        if (prev == null || prev.left == curr || prev.right == curr) { // traverse down the tree 
            if (curr.left != null) { 
                stack.push(curr.left); 
            } else if (curr.right != null) { 
                stack.push(curr.right); 
            } 
        } else if (curr.left == prev) {                         // traverse up the tree from the left 
            if (curr.right != null) { 
                stack.push(curr.right); 
            } 
        } else {                                                // traverse up the tree from the right 
            result.add(curr.val); 
            stack.pop(); 
        } 
        prev = curr; 
    } 
    return result; 
}

public List<Integer> postorderTraversal(TreeNode root) {
    LinkedList<Integer> res = new LinkedList<>();
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
      TreeNode cur = stack.pop();
      if (cur == null) continue;
      res.addFirst(cur.val);
      stack.push(cur.left);   // LEFT first
      stack.push(cur.right); //  RIGHT behind
    }
    return res;
  }

BFS（Level-Order）

这道题有好多种变换：而且要2种都会，不光是递归，迭代两种

1. bottom-up 的方式来Level Traversal，可以reverse 链表，也可以在头部插入，ans.add(0, level)
2. Zig-zag 的方式来Traversal ，

Iterative:

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> ans = new ArrayList<>();
    if (root == null) return ans;
    Deque<TreeNode> queue = new ArrayDeque<TreeNode>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        List<Integer> level = new ArrayList<Integer>();

        for (int i = 0; i < size; i++) {
             TreeNode cur = queue.poll();
             level.add(cur.val);
             if (cur.left != null) { queue.offer(cur.left);}
             if (cur.right != null) { queue.offer(cur.right);}
        }
        ans.add(level);
     }
     return ans;
}

Recursive:

• when we recursive right first, we will get rightmost one.
• do not need put in whole nodes in map when deal with right side view.

public List<List<Integer>> levelOrder(TreeNode root) { 
    List<List<Integer>> res = new ArrayList<List<Integer>>(); // 用第一层的List纪录Level的Depth
    levelHelper(res, root, 0); 
    return res; 
} 
public void levelHelper(List<List<Integer>> res, TreeNode root, int height) {
    if (root == null) return; 
    if (height >= res.size()) {        // 这里跟backtracking不同的是已经构建好框架，如果不够的话直接在上面补
        res.add(new LinkedList<Integer>()); 
    } 
    res.get(height).add(root.val); 
    levelHelper(res, root.left, height+1); 
    levelHelper(res, root.right, height+1); 
}

Binary Tree Right Side View

public class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<Integer>();
        rightView(root, result, 0);
        return result;
    }

    public void rightView(TreeNode curr, List<Integer> result, int currDepth){
        if(curr == null){
            return;
        }
        if(currDepth == result.size()){
            result.add(curr.val);
        }

        rightView(curr.right, result, currDepth + 1);
        rightView(curr.left, result, currDepth + 1);

    }
}

Leaf's Order Traversal

private int findLeavesHelper(List<List<Integer>> list, TreeNode root) {
    if (root == null) return -1;  
    int leftLevel = findLeavesHelper(list, root.left);       //
    int rightLevel = findLeavesHelper(list, root.right);     //
    int level = Math.max(leftLevel, rightLevel) + 1;         // height

    if (list.size() == level) {                              //
        list.add(new ArrayList<>()); 
    } 
    list.get(level).add(root.val);                           //
    root.left = root.right = null; 
    return level; 
}

Vertical Order Traversal

垂直的方式进行, 由左到右进行Order Traversal

• 每一层相当于到Root的距离，那么每次在遍历的时候需要把距离纪录下来，并且存到一个 Level 为 Key的Map里面
• 要用到两个Queue来装，一个是来装TreeNode， 一个来装Distance
• 在纪录Key(Distance)的时候，要知道区间。Min --> Max