我正在编写用于二叉树层序遍历的 c++ 函数,
但它并没有打印所有级别,有人能告诉我这段代码有什么问题吗?这是我的代码:##
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector< vector<int> > res;
TreeNode* ptr;
queue<TreeNode*> q;
vector<int> v;
if(root){
q.push(root);
q.push(NULL);
}
while(!(q.empty())){
ptr = q.front();
q.pop();
if(q.empty())
break;
if(ptr){
if(ptr->left)
q.push(ptr->left);
if(ptr->right)
q.push(ptr->right);
v.push_back(ptr->val);
}
else {
q.push(NULL);
res.push_back(v);
v.clear();
}
}
return res;
}
};
总结这段代码的整体逻辑:
1) 维护一个队列,每个级别的节点都被插入该队列,并在每个级别的最后一个元素之后推送一个 NULL
指针。该算法首先将根元素插入队列,然后是 NULL
。
2) 每个级别的元素都从队列中弹出,并且它的子元素立即被推回队列中。
3) 当 NULL
指针从队列中弹出时,这一定意味着队列没有充满下一级的元素,因此 NULL
会立即被压入回到队列中。
4) 代码首先将队列中的所有元素收集到临时缓冲区 v
中。当 NULL
指针从队列中弹出时,v
现在包含二叉树中单个级别上的所有元素,并且 v
得到 push_back()
进入 res
,此函数的返回值。
错误出现在这段代码中:
ptr = q.front();
q.pop();
if(q.empty())
break;
这会从队列中移除下一个元素。如果元素被移除后队列为空,则算法终止。
此处的意图是队列中最后的、最终的、剩余的值始终是树中最低级别最后一个值末尾的 NULL
指针。队列现已完全耗尽,算法终止。
不幸的是,该算法已从 v
vector 中的树中的最低级别收集了所有值,并且完全跳过了以下保存它们的代码部分:
q.push(NULL);
res.push_back(v);
v.clear();
push_back()
永远不会在树的底层执行。此函数的最终结果永远不会包括二叉树中的最低层。
将终止条件更改为:
if(q.empty())
{
res.push_back(v);
break;
}
我是一名优秀的程序员,十分优秀!