Leetcode116. Populating Next Right Pointers in Each Node填充同一层的兄弟节点
2024-10-07 20:03:21
给定一个二叉树
struct TreeLinkNode { TreeLinkNode *left; TreeLinkNode *right; TreeLinkNode *next; }
填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL。
初始状态下,所有 next 指针都被设置为 NULL。
说明:
- 你只能使用额外常数空间。
- 使用递归解题也符合要求,本题中递归程序占用的栈空间不算做额外的空间复杂度。
- 你可以假设它是一个完美二叉树(即所有叶子节点都在同一层,每个父节点都有两个子节点)。
示例:
给定完美二叉树,
1 / \ 2 3 / \ / \ 4 5 6 7
调用你的函数后,该完美二叉树变为:
1 -> NULL / \ 2 -> 3 -> NULL / \ / \ 4->5->6->7 -> NULL
class Solution {
public:
void connect(TreeLinkNode *root)
{
if(root == NULL)
return;
queue<TreeLinkNode*> q;
q.push(root);
while(!q.empty())
{
int len = q.size();
for(int i = 0; i < len; i++)
{
TreeLinkNode *node = q.front();
q.pop();
node ->next = i == len - 1? NULL : q.front();
if(node ->left)
q.push(node ->left);
if(node ->right)
q.push(node ->right);
}
}
}
};
最新文章
- 红帽RHEL7版本RHCE认证学习及考试经历
- 浅谈javascript中事件冒泡与事件捕获
- matlab global 不能传向量/矩阵
- HDU 1878 欧拉回路
- 第二课:判断js变量的类型以及domReady的原理
- firebug console使用
- ecshop的smarty库还原成smarty原生库方法
- 一天一个mysql函数(二) FIND_IN_SET()
- Android:反编译查看源码
- Jdbc 事务
- java集合--Queue用法
- Linux五种IO模型性能分析
- sqlserver isnull判断
- (三十一)PickerView自定义视图
- laravel+Redis简单实现队列通过压力测试的高并发处理
- Senparc.Weixin.TenPay 正式发布
- 关于Select2下拉框组件
- 移除input框type=";number";在部分浏览器的默认上下按钮
- swift的异常处理:本质是错误信息的传递方式
- linux split 切割大文件