107 Binary Tree Level Order Traversal II

107. Binary Tree Level Order Traversal II
1. Question
Given a binary tree, return thebottom-up level ordertraversal of its nodes' values. (ie, from left to right, level by level from leaf to root).
For example:
Given binary tree[3,9,20,null,null,15,7],
1
    3
2
   / \
3
  9  20
4
    /  \
5
   15   7
Copied!
return its bottom-up level order traversal as:
1
[
2
  [15,7],
3
  [9,20],
4
  [3]
5
]
Copied!
2. Implementation
(1) BFS
1
class Solution {
2
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
3
        List<List<Integer>> res = new ArrayList<>();
4
​
5
        if (root == null) {
6
            return res;
7
        }
8
​
9
        Queue<TreeNode> queue = new LinkedList<>();
10
        queue.add(root);
11
​
12
        List<Integer> level = null;
13
​
14
        while (!queue.isEmpty()) {
15
            int size = queue.size();
16
            level = new ArrayList<>();
17
​
18
            for (int i = 0; i < size; i++) {
19
                TreeNode curNode = queue.remove();
20
                level.add(curNode.val);
21
​
22
                if (curNode.left != null) {
23
                    queue.add(curNode.left);
24
                }
25
​
26
                if (curNode.right != null) {
27
                    queue.add(curNode.right);
28
                }
29
            } 
30
            res.add(0, level);
31
        }
32
        return res;
33
    }
34
}
Copied!
(2) DFS
1
class Solution {
2
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
3
        List<List<Integer>> res = new ArrayList<>();
4
        getLevelOrderByDFS(root, 0, res);
5
        return res;
6
    }
7
​
8
    public void getLevelOrderByDFS(TreeNode node, int depth, List<List<Integer>> res) {
9
        if (node == null) {
10
            return;
11
        }
12
​
13
        if (res.size() == depth) {
14
            res.add(0, new ArrayList<>());
15
        }
16
        res.get(res.size() - depth - 1).add(node.val);
17
​
18
        getLevelOrderByDFS(node.left, depth + 1, res);
19
        getLevelOrderByDFS(node.right, depth + 1, res);
20
    }
21
}
Copied!
3. Time & Space Complexity
BFS: 时间复杂度: O(n), 空间复杂度: O(n)
DFS: 时间复杂度: O(n), 空间复杂度: O(n)

104 Maximum Depth of Binary Tree

108 Convert Sorted Array to Binary Search Tree

Last modified 2yr ago

Copy link

Contents

107. Binary Tree Level Order Traversal II

1. Question

2. Implementation

3. Time & Space Complexity