题目来源:https://leetcode.com/problems/binary-tree-level-order-traversal-ii/description/

标记难度:Easy

提交次数:3/3

代码效率:

  • 递推:0.00%
  • reverse:98.33%
  • 两次DFS:98.33%

题意

返回一棵二叉树自底向上的层次遍历。

分析

这次我用上了Leetcode 429里面的那种递推法。[1]leftLevels表示当前结点左子树的自底向上层次遍历结果,rightLevels表示当前结点左子树的自底向上层次遍历结果。显然,左右两侧的深度不同,所以我们需要把它们“自顶向下”合并。以leftLevels.size > rightLevels的情形为例:

1
2
3
4
5
6
7
8
9
10
11
12
13
n1 = leftLevels.size, n2 = rightLevels.size

leftLevels[0] --> levels[0]
leftLevels[1] --> levels[1]
. .
. .
. .
leftLevels[n1-n2] + rightLevels[0] --> levels[n1-n2]
leftLevels[n1-n2+1] + rightLevels[1] --> levels[n1-n2+1]
. . .
. . .
. . .
leftLevels[n1-1] + rightLevels[n2-1] --> levels[n1-1]

当然,我们都知道,最简单的一种方法就是做一次普通的层次遍历,然后把整个vector倒转过来。不过这种解法就很平凡了。[2]

另一种不那么平凡的方法是,首先进行一次DFS,得到树的深度;然后再进行一次DFS,此时我们就可以得到结点在层次遍历中应有的位置,然后直接把结点插入对应的vector中即可。

一个很有趣的问题是,如果vector能够以O(1)时间在头部插入的话,这个问题和正向层次遍历就是正好对偶的了。对于Java用户,他们的函数返回值是List<List<int>>,因此可以通过LinkedList达到一种比较好的效果。[3]

代码

递推

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
vector<vector<int>> levelOrderBottom(TreeNode* root) {
if (root == nullptr) return {};
vector<vector<int>> leftLevels = levelOrderBottom(root->left);
vector<vector<int>> rightLevels = levelOrderBottom(root->right);
int n1 = leftLevels.size(), n2 = rightLevels.size(), n = max(n1, n2);
vector<vector<int>> levels(n + 1, vector<int>());
// i表示从数组末端开始的距离,也即对应的层相对root的深度
// 这样表示是因为数组是末端对齐的
for (int i = n; i > 0; i--) {
if (n1 - i >= 0)
levels[n - i].insert(levels[n - i].end(), leftLevels[n1 - i].begin(), leftLevels[n1 - i].end());
if (n2 - i >= 0)
levels[n - i].insert(levels[n - i].end(), rightLevels[n2 - i].begin(), rightLevels[n2 - i].end());
}
levels[n].push_back(root->val);
return levels;
}
};

reverse

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
private:
vector<vector<int>> levels;

void dfs(TreeNode* root, int depth) {
if (root == NULL) return;
if (levels.size() <= depth) levels.push_back({});
levels[depth].push_back(root->val);
dfs(root->left, depth+1);
dfs(root->right, depth+1);
}

public:
vector<vector<int>> levelOrderBottom(TreeNode* root) {
dfs(root, 0);
reverse(levels.begin(), levels.end());
return levels;
}
};

两次DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
private:

int maxDepth;

void getMaxDepth(TreeNode* root, int depth) {
if (root == nullptr) return;
maxDepth = max(maxDepth, depth);
getMaxDepth(root->left, depth+1);
getMaxDepth(root->right, depth+1);
}

void dfs(TreeNode* root, int depth, vector<vector<int>>& levels) {
if (root == nullptr) return;
levels[maxDepth - depth].push_back(root->val);
dfs(root->left, depth+1, levels);
dfs(root->right, depth+1, levels);
}

public:
vector<vector<int>> levelOrderBottom(TreeNode* root) {
maxDepth = -1;
getMaxDepth(root, 0);
vector<vector<int>> levels(maxDepth+1, vector<int>());
dfs(root, 0, levels);
return levels;
}
};

  1. Easy to understand, recursive solution based on DFS (44 ms, beats 98.67%)

  2. C++ 4ms solution!

  3. Simple Java solution with LinkedList.

题目来源:https://leetcode.com/problems/n-ary-tree-level-order-traversal/description/

标记难度:Easy

提交次数:2/3

代码效率:

  • 未优化的BFS:5.07%
  • DFS:36.95%
  • 不同的DFS写法:10.52%

题意

返回一棵多叉树的层次遍历结果。不同层要分开。

分析

直接BFS即可。不过我感觉我有点傻,每一层都新开了一个队列;事实上不需要,只要记录当前层的结点个数就足以判断何时这一层结束了。[1]中间WA了一次,是因为对于空结点应该返回[],而非[[]]。(我似乎经常在这一点上犯错。)

另一种相对比较神奇的做法是用DFS。此时的核心问题是不同的子结点返回的层次遍历结果的合并:显然,子结点的层次遍历结果总是比当前结点正好低一层。令r = levelOrder(root->child)ret表示当前结点的层次遍历结果。显然,r[0]应该与ret[1]合并,r[1]应该与ret[2]合并,以此类推。[2]

看了Java Solution using DFS之后,我重写了一份看起来会跑得更快的DFS,但事实上并没有。

以及,从上述代码里我学习了把一个vector里的内容(而不是整个vector)插入到别的vector里的正确方法[3]

1
2
3
// 在 pos 前插入来自范围 [first, last) 的元素。
template< class InputIt >
void insert( iterator pos, InputIt first, InputIt last);

代码

未优化的BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/*
// Definition for a Node.
class Node {
public:
int val = NULL;
vector<Node*> children;

Node() {}

Node(int _val, vector<Node*> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public:
vector<vector<int>> levelOrder(Node* root) {
if (root == NULL) return {};

vector<vector<int>> levelOrder;
queue<Node*> q1;
q1.push(root);

while (!q1.empty()) {
vector<int> level;
queue<Node*> q2;
while (!q1.empty()) {
Node* x = q1.front();
q1.pop();
level.push_back(x->val);
for (Node* c: x->children)
q2.push(c);
}
q1 = q2;
levelOrder.push_back(level);
}

return levelOrder;
}
};

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/*
// Definition for a Node.
class Node {
public:
int val = NULL;
vector<Node*> children;

Node() {}

Node(int _val, vector<Node*> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public:
vector<vector<int>> levelOrder(Node* root) {
if (root == NULL) return {};
vector<vector<int>> level;
level.push_back({root->val});
for (Node* child: root->children) {
vector<vector<int>> chLevel = levelOrder(child);
for (int i = 0; i < chLevel.size(); i++) {
if (i < level.size() - 1)
level[i + 1].insert(level[i + 1].end(), chLevel[i].begin(), chLevel[i].end());
else
level.push_back(chLevel[i]);
}
}
return level;
}
};

另一种DFS写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/*
// Definition for a Node.
class Node {
public:
int val = NULL;
vector<Node*> children;

Node() {}

Node(int _val, vector<Node*> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
private:
void dfs(Node* root, int depth, vector<vector<int>>& levels) {
if (root == NULL) return;
if (depth < levels.size())
levels[depth].push_back(root->val);
else
levels.push_back({root->val});
for (Node* ch: root->children)
dfs(ch, depth+1, levels);
}

public:
vector<vector<int>> levelOrder(Node* root) {
vector<vector<int>> levels;
dfs(root, 0, levels);
return levels;
}
};

  1. Basic C++ solution using queue. Super easy for beginners.

  2. Easy to understand, recursive solution based on DFS (44 ms, beats 98.67%)

  3. std::vector::insert