我在网上找到了一个按关卡顺序遍历二叉树的程序。 下面的代码传递并生成所需的输出:
class Solution {
public:
std::vector< vector< int >> res;
void buildVec(TreeNode* root, int level) {
if(root==NULL)
return;
if(res.size()==level)
res.push_back(vector< int >());
res[level].push_back(root->val);
buildVec(root->left, level+1);
buildVec(root->right, level+1);
}
vector<vector<int>> levelOrder(TreeNode* root) {
res.clear();
buildVec(root, 0);
return res;
}
};
我不明白的是这样的说法:if(res.size()==level)
. 这句话究竟达到了什么目的? 当级别为 2 时,最多可以有 4 个元素(因为级别从 0 开始),这大于标签 (2) 的值。 那么,这种说法是如何运作的呢?
编辑:因此,如果输入是:
3
/
9 20
/
15 7
则返回的输出将是
[
[3],
[9,20],
[15,7],
]
这样做的原因是为了避免第二次递归调用buildVec
在结果向量的末尾添加另一个级别向量,即使第一次调用已经为此特定级别添加了另一个级别向量。
最简单的方法是在示例树上运行一个没有 15 和 7 的示例运行,从而弄清楚发生了什么。
levelOrder
做的第一件事是清空res
向量。然后它调用buildVec(root, 0)
.在那里root
不等于NULL
,但它保持res.size() = 0 = level
,所以一个空向量被附加到res
,从而res = [[]]
。在下一步中,当前节点的值被推入新附加的向量中。所以res = [[3]]
.
然后调用buildVec(root->left, 1)
。在那里,root
又不是 NULL 而是res.size() = 1 = level
,所以另一个空向量附加到res
上,因此res = [[3], []]
。我们将值 9 插入到res[1]
中,所以现在res = [[3], [9]]
.
当调用buildVec(root->left, 2)
和buildVec(root->right, 2)
时,没有任何反应,因为两个子级都不存在,即在这些调用中root == NULL
返回 true。
所以我们继续通话buildVec(root->right, 1)
.在这里,第一次,res.size() = 2 != 1 = level
.所以我们不附加一个新的向量。然后我们将值20
插入到res[1]
中。所以res = [[3], [9, 20]]
.
如果检查res.size() == level
不存在,我们将在末尾附加一个新的空向量,因此结果将改为res = [[3], [9, 20], []]
。
但事实证明,检查是不正确的。如果将树翻转到
3
/
20 9
/
15 7
它将返回[[3], [20, 9], [15, 7], []]
. 正确的检查是res.size() <= level
.
if(res.size()==level)
res.push_back(vector< int >());
此语句只是为了在res
中添加另一个向量以获得新级别。
3
/
9 20
/
15 7
让我们以节点15
级别2
。res
的值将是[[3], [9, 20]]
和res.size() == 2
,条件将为 true,因此它将为新级别创建一个新向量并将节点15
插入其中,同样对于节点7
条件将为 false,因为res.size()
将变得3
因此节点将入res[level]
向量中而不创建新向量。