【Leetcode】【Medium】Populating Next Right Pointers in Each Node
2024-08-25 16:02:49
Given a binary tree
struct TreeLinkNode {
TreeLinkNode *left;
TreeLinkNode *right;
TreeLinkNode *next;
}
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL
.
Initially, all next pointers are set to NULL
.
Note:
- You may only use constant extra space.
- You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).
For example,
Given the following perfect binary tree,
1
/ \
2 3
/ \ / \
4 5 6 7
After calling your function, the tree should look like:
1 -> NULL
/ \
2 -> 3 -> NULL
/ \ / \
4->5->6->7 -> NULL
解题思路:
建立两个指针,一个指针用于操作父节点,给孩子结点的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) {
TreeLinkNode *cur = root;
TreeLinkNode *layer_first = root; if (!root)
return; while (layer_first->left) {
cur->left->next = cur->right;
if (cur->next) {
cur->right->next = cur->next->left;
cur = cur->next;
} else {
layer_first = layer_first->left;
cur = layer_first;
}
} return;
}
};
最新文章
- sqlite索引的原理
- ThinkPHP + Discuz 整合方法
- activiti自定义流程之整合(四):整合自定义表单部署流程定义
- CentOS7安装RabbitMQ集群
- react-redux原理
- 关于51单片机P0口的结构及上拉问题
- 微软雅黑 firefox Css 设置	font-family: ";microsoft yahei";,";\5FAE\8F6F\96C5\9ED1";,";宋体";;
- javascript - C++, Qt, QtWebKit: How to create an html rendering window so that your application would get callbacks from JS calls? - Stack Overflow
- Web服务器、应用服务器、Web容器、反向代理服务器区别与联系
- opencv人脸检测,旋转处理
- docker+httpd的安装
- 【工具相关】Web-ionic-ionicLab的使用
- BAI度 内部资料!Python_Threads多线程
- Ajax csrf跨站请求伪造
- 启动weblogic报错:string value '2.4' is not a valid enumeration value for web-app-versionType in namespace http://java.sun.com/xml/ns/javaee
- BZOJ3613 南园满地堆轻絮 二分/贪心
- jedata日期控件的开始结束日期设置
- 几个简单常用的jQuery实例
- HDU3625(SummerTrainingDay05-N 第一类斯特林数)
- Swift 项目中可能用到的第三方框架