LeetCode OJ:Populating Next Right Pointers in Each Node II(指出每一个节点的下一个右侧节点II)
2024-08-28 01:00:00
Follow up for problem "Populating Next Right Pointers in Each Node".
What if the given tree could be any binary tree? Would your previous solution still work?
Note:
- You may only use constant extra space.
For example,
Given the following binary tree,
1
/ \
2 3
/ \ \
4 5 7
After calling your function, the tree should look like:
1 -> NULL
/ \
2 -> 3 -> NULL
/ \ \
4-> 5 -> 7 -> NULL
指出每个节点的下一个右侧节点,前一篇博客的那个思路也可以继续使用,但由于这里的二叉树是任意的,所以应该用函数找到下一层的开始节点以及下一层的下一个节点,代码如下:
class Solution{
public:
void connect(TreeLinkNode *root)
{
TreeLinkNode * prev, * curr, * start;
if(!root) return;
while(root){
start = findNextLevelStartNode(root);
prev = start;
curr = findNextLevelNextNode(root, prev);
while(curr){
prev->next = curr;
prev = curr;
curr = findNextLevelNextNode(root, curr);
}
root = start;
}
}
private:
TreeLinkNode * findNextLevelNextNode(TreeLinkNode * & node, TreeLinkNode * curr)//注意使用引用
{
if(node->left == curr && node->right)
return node->right;
else{
while(node->next){
node = node->next;
if(node->left != NULL && node->left != curr) return node->left;
if(node->right != NULL && node->right != curr) return node->right;
}
}
return NULL;
} TreeLinkNode * findNextLevelStartNode(TreeLinkNode * node)
{
if(!node) return NULL;
if(node->left)
return node->left;
else return findNextLevelNextNode(node, node->left);
}
};
最新文章
- SSIS Design3:并发执行
- ASP.NET MVC进阶三
- 让我们来讲讲,SCRUM和AGILE(资料来源:https://www.youtube.com/ 文中有代理参数配置)
- 【2016-10-12】【坚持学习】【Day3】【命令模式】
- CodeForces 670E Correct Bracket Sequence Editor(list和迭代器函数模拟)
- hdu 5927 Auxiliary Set 贪心
- armp启动
- How to Configure the Gradient Boosting Algorithm
- STL源码学习----lower_bound和upper_bound算法[转]
- zedboard--Opencv移植和zedboard测试(十一)
- rsyslog masg和rawmsg的区别
- Skynumber
- 【Unity3D】Unity3D开发《我的世界》之六、创建地形(视频 + 源码)
- java游戏开发杂谈 - 事件处理
- wGenerator代码生成工具
- 纠错式教学法对比鼓励式教学法 -----Lily、贝乐、英孚,乐加乐、剑桥国际、优学汇、北外青少
- c/c++ 网络编程 UDP 发送端 bind 作用
- 用PowerShell的命令行检查文件的校验MD5 SHA1 SHA256
- 安装OpenSSL中出现的问题及解决
- python315题