Level Order Traversal

102. Binary Tree Level Order Traversal

Java

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

// DFS
public void helper(TreeNode node, int level, List<List<Integer>> results) {
if (results.size() == level) {
  results.add(new ArrayList<>());
}
results.get(level).add(node.val);
if (node.left != null) helper(node.left, level + 1, results);
if (node.right != null) helper(node.right, level + 1, results);
}

Python

    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return None
        queue = []
        list = []
        level = 0
        queue.append(root)
        while queue:
            list.append([])
            # length = len(queue)
            for i in range(0, len(queue)):
                curt = queue.pop(0)
                list[level].append(curt.val)
                if curt.left:
                    queue.append(curt.left)
                if curt.right:
                    queue.append(curt.right)
            level += 1
        return list

107. Binary Tree Level Order Traversal II

BFS: Reverse result by using Collections.reverse(results);

// BFS
public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> results = new ArrayList<>();
    if (root == null) {
        return results;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        List<Integer> curtLevel = new ArrayList<>();
        int size = queue.size();
        for (int i = 0 ; i < size; i++) {
            TreeNode head = queue.poll();
            curtLevel.add(head.val);
            if (head.left != null) {
                queue.offer(head.left);
            }
            if (head.right != null) {
                queue.offer(head.right);
            }
        }
        results.add(curtLevel);
    }
    Collections.reverse(results);
    return results;
}

// DFS
public List<List<Integer>> levelOrderBottom(TreeNode root) {
    if (root == null) return new ArrayList<>();
    List<List<Integer>> result = new ArrayList<>();
    helper(result, root, 0);
    return result;
}

private void helper(List<List<Integer>> result, 
                   TreeNode node,
                   int level) {
    if (node == null) return;
    if (level >= result.size()) {
        result.add(0, new ArrayList<>());
    }
    helper(result, node.left, level + 1);
    helper(result, node.right, level + 1);
    result.get(result.size() - level - 1).add(node.val);
}

103. Binary Tree Zigzag Level Order Traversal

Reverse order when it is in odd level.

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    Queue<TreeNode> q= new LinkedList<>();
    q.offer(root);
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) return res;
    int level = 0;
    while (!q.isEmpty()) {
        int size = q.size();
        List<Integer> levelList = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            TreeNode curt = q.poll();
            levelList.add(curt.val);
            if (curt.left != null) q.offer(curt.left);
            if (curt.right != null) q.offer(curt.right);
        }
        if (level % 2 == 1) reverse(levelList);
        res.add(levelList);
        level++;
    }
    return res;
}
private void reverse(List<Integer> list) {
    int i = 0, j = list.size() - 1;
    while (i < j) {
        int temp = list.get(i);
        list.set(i, list.get(j));
        list.set(j, temp);
        i++;
        j--;
    }
}

513. Find Bottom Left Tree Value

Replace result when the curt node is the first of each level

public int findBottomLeftValue(TreeNode root) {
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    TreeNode res = root;
    while (!q.isEmpty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            TreeNode curt = q.poll();
            if (i == 0) res = curt;
            if (curt.left != null) q.offer(curt.left);
            if (curt.right != null) q.offer(curt.right);
        }
    }
    return res.val;
}

958. Check Completeness of a Binary Tree

BFS traverse this tree. Add children of node to the tree. Break if reach null. Pop all nodes in the queue, there are not null nodes, this means there is a sequence of null -> node -> null in the queue, which is not a complete tree.

public boolean isCompleteTree(TreeNode root) {
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);
    while (true) {
        TreeNode curt = q.poll();
        if (curt == null) {
            break;
        } else {
            q.offer(curt.left);
            q.offer(curt.right);
        }
    }
    while (!q.isEmpty()) {
        if (q.poll() != null) return false;
    }
    return true;
}

919. Complete Binary Tree Inserter

Move all nodes to the very left by using queue. When insert, check if the left node is null, then insert on left. Otherwise insert on right, then add left + right nodes to queue, and poll curt.

class CBTInserter {
    private final TreeNode root;
    private final Queue<TreeNode> q;
    
    public CBTInserter(TreeNode root) {
        this.root = root;
        q = new LinkedList<>();
        q.offer(root);
        while (q.peek().right != null) {
            q.offer(q.peek().left);
            q.offer(q.poll().right);
        }
    }
    
    public int insert(int v) {
        TreeNode p = q.peek();
        if (p.left == null) {
            p.left = new TreeNode(v);
        } else {
            p.right = new TreeNode(v);
            q.poll();
            q.offer(p.left);
            q.offer(p.right);
        }
        return p.val;
    }
    
    public TreeNode get_root() {
        return root;
    }
}