【leetcode】Populating Next Right Pointers in Each Node II
2024-08-27 12:03:12
Populating Next Right Pointers in Each Node II
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
与I的思路类似
left->next=father->right
right->next=father->next->left;
只是当我们没有找到时,father=father->next;
需要注意,先搜索右子树,再搜索左子树
/**
* Definition for binary tree with next pointer.
* struct TreeLinkNode {
* int val;
* TreeLinkNode *left, *right, *next;
* TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
* };
*/
class Solution {
public:
void connect(TreeLinkNode *root) { if(root==NULL)
{
return;
} if(root->left!=NULL)
{
if(root->right!=NULL)
{
root->left->next=root->right;
}
else
{
TreeLinkNode *tmp=root->next;
root->left->next=NULL;
while(tmp!=NULL)
{
if(tmp->left!=NULL)
{
root->left->next=tmp->left;
break;
} if(tmp->right!=NULL)
{
root->left->next=tmp->right;
break;
}
tmp=tmp->next;
}
}
} if(root->right!=NULL)
{
TreeLinkNode *tmp=root->next;
root->right->next=NULL;
while(tmp!=NULL)
{
if(tmp->left!=NULL)
{
root->right->next=tmp->left;
break;
} if(tmp->right!=NULL)
{
root->right->next=tmp->right;
break;
}
tmp=tmp->next;
}
} connect(root->right);
connect(root->left); }
};
最新文章
- Jingle 相关问题
- chmod 和 chown 的用法
- 山东理工大学第七届ACM校赛-飞花的鱼塘 分类: 比赛 2015-06-26 10:30 43人阅读 评论(0) 收藏
- 使用ViewPager+Fragment来实现带滚动条的多屏滑动-IndicatorFragmentActivity
- 关于python抓取google搜索结果的若干问题
- MySQL学习笔记之中的一个 MySQL入门
- .NET面试题目二
- 关于js中window.location.href,location.href,parent.location.href,top.location.href用法
- javascript . 05 json的组成、for...in 遍历对象、简单数据类型与复杂数据类型的传值与传址、内置对象
- php session 和cookie
- mysql中的视图、事务和索引
- sql的having深入理解;group by只返回一组的一行,compute更好
- javascript内置对象速查(一)
- python自定义pi函数的代码
- KNN算法基本实例
- 伪静态与重定向--RewriteBase
- Spring+CXF整合来管理webservice(服务器启动发布webservice)
- idea中maven中jdk版本的选择(转)
- Indy Changed from Indy10
- 什么是 CLR(转)