Binary TreeNode class

/**
* Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

BFS

https://leetcode.com/problems/binary-tree-level-order-traversal/description/

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> valuesByLevel = new ArrayList<>();
    if (root == null) {
        return valuesByLevel;
    }
    
    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    queue.offer(root);
    
    while (!queue.isEmpty()) {
        ArrayList<Integer> level = new ArrayList<>();
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
        valuesByLevel.add(level);
    }
    
    return valuesByLevel;
}

---

DFS: Preorder

https://leetcode.com/problems/binary-tree-preorder-traversal/description/

iteration

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> res = new LinkedList<>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode runner = root;
    
    while (runner != null || !stack.isEmpty()) {
        if (runner == null) {
            runner = stack.pop();
        }
        res.add(runner.val);
        if (runner.right != null) {
            stack.push(runner.right);
        }
        runner = runner.left; // not checking null or not. null indicates stack need to pop
    }
    
    return res;
}

recursion

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> res = new ArrayList<Integer>();
    preorderHelper(root, res);
    return res;
}

private void preorderHelper(TreeNode node, List<Integer> res) {
    if (node == null) {
        return;
    }
    res.add(node.val);
    preorderHelper(node.left, res);
    preorderHelper(node.right, res);
}

---

DFS: Inorder

https://leetcode.com/problems/binary-tree-inorder-traversal/description/

iteration

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> res = new LinkedList<>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode runner = root;
    
    while (runner != null || !stack.isEmpty()) {
        while (runner != null) {
            stack.push(runner);
            runner = runner.left;
        }
        runner = stack.pop();
        res.add(runner.val);
        runner = runner.right;
    }
    
    return res;
}

recursion

public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> res = new LinkedList<>();
    inorderHelper(root, res);
    return res;
}

private void inorderHelper(TreeNode node, List<Integer> res) {
    if (node == null) {
        return;
    }
    
    inorderHelper(node.left, res);
    res.add(node.val);
    inorderHelper(node.right, res);
}

divide & conquer

// a version of recursion
leftRes = ...
rightRes = ...
res = (leftRes, rightRes, currentNode)

no extra space, in place

modify the Tree object to make it like a list.

---

DFS: Postorder

https://leetcode.com/problems/binary-tree-postorder-traversal/description/

iteration

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> res = new LinkedList<Integer>();
    Stack<TreeNode> stack = new Stack<>();
    TreeNode runner = root;
    
    while (runner != null || !stack.isEmpty()) {
        while (runner != null) {
            stack.push(runner);
            runner = runner.left;
            if (runner == null) {
                runner = stack.peek().right;
            }
        }
        
        runner = stack.pop();
        res.add(runner.val);
        
        // 如果 runner 为 rightChild, pop;
        // 如果 runner 为 leftChild，更新 runner 为 parent.rightChild.
        while (!stack.isEmpty() && runner == stack.peek().right) {
            runner = stack.pop();
            res.add(runner.val);
        }
        
        runner = stack.isEmpty() ? null : stack.peek().right;
    }
    
    return res;
}

recursion

public List<Integer> postorderTraversalRecursive(TreeNode root) {
    List<Integer> res = new LinkedList<Integer>();
    postorderTraversalHelper(res, root);
    return res;
}

private void postorderTraversalHelper(List<Integer> res, TreeNode root) {
    if (root == null) {
        return;
    }

    postorderTraversalHelper(res, root.left);
    postorderTraversalHelper(res, root.right);
    res.add(root.val);
}