Tree Traversal

Binary Tree Level Order Traversal

★☆☆☆☆

BFS

public class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if (root == null) return new LinkedList<List<Integer>>();
        List<List<Integer>> ans = new LinkedList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> curVals = new LinkedList<>();
            int qSize = queue.size(); 
            //Cant do it in loop, will check size every time then fail
            for (int i = 0; i < qSize; ++i) {
                TreeNode node = queue.poll();
                curVals.add(node.val);
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            ans.add(curVals);
        }
        return ans;
    }
}

Binary Tree Level Order Traversal II

★★☆☆☆

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root). {3,9,20,#,#,15,7} should return [[15,7], [9,20], [3]]

public class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> ans = new LinkedList<>();
        dfs(root, 0, ans);
        return ans;
    }
    public void dfs(TreeNode node, int level, List<List<Integer>> ans) {
        if (node == null) return;
        if (level >= ans.size()) ans.add(0, new LinkedList<Integer>());
        ans.get(ans.size() - level - 1).add(node.val); //index is the crutial part!!
        if (node.left != null) dfs(node.left, level + 1, ans);
        if (node.right != null) dfs(node.right, level + 1, ans);
    }
}

Morris In-Order Traversal

★★★☆☆

Notes:

• ref cite
• 
• "it's your turn" only when left subtree has already been done (or is null)
• preNode.right != root in while (preNode.right != null && preNode.right != root) works as the flag of already traversing the left subtree or not!
• preNode.right != null imply preNode.right == root (since you already go right deepest in the while loop)

while (node != null) {
    if (node.left == null) {
        System.out.println(node.val);//"it's my turn"
        node = node.right;
    }
    else {
        TreeNode preNode = node.left;
        while (preNode.right != null && preNode.right != node)
            preNode = preNode.right;//find node previous to node
        if (preNode.right == null) {//first time go to node
            preNode.right = node;//morris connection!
            node = node.left;//keep searching down!
        }
        else {
        //should always satisfy preNode.right == node
        //since it's second time arrive here, and left sub-tree has been done
            preNode.right = null;//recover the tree structure
            System.out.println(node.val);//"it's your turn"
            node = node.right;
        }
    }
}

Binary Tree Right Side View

★★☆☆☆

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

For example: Given the following binary tree,

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

You should return [1, 3, 4].

Note

• Always go right first
• right side view's depth should be equal to current size of result list.

public List<Integer> rightSideView(TreeNode root) {
    return dfs(root, new ArrayList<Integer>(), 0);
}
public List<Integer> dfs(TreeNode node, List<Integer> ans, int depth) {
    if (node == null) return ans;
    if (depth == ans.size()) ans.add(node.val);
    dfs(node.right, ans, depth + 1);
    dfs(node.left, ans, depth + 1);
    return ans;
}