Populating Next Right Pointers in Each Node I&&II ——II仍然需要认真看看
2024-08-25 22:07:35
Populating Next Right Pointers in Each Node I
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
乍一看很难，理清思路后很简单的。
/**
* 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||root->left==NULL)
return;
root->left->next=root->right;
if(root->next!=NULL)
root->right->next=root->next->left;
connect(root->left);
connect(root->right);
return ;
}
};
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
/**
* 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(NULL == root) return;
TreeLinkNode* start;
TreeLinkNode* curNode;
TreeLinkNode* nextNode;
while(root != NULL){
start = findStartNodeNextLev(root);
curNode = start;
nextNode = findNextNodeNextLev(root, start);
while(nextNode != NULL){
curNode -> next = nextNode;
curNode = nextNode;
nextNode = findNextNodeNextLev(root, curNode);
}
root = start;
}
}
private:
TreeLinkNode* findNextNodeNextLev(TreeLinkNode* &cur, TreeLinkNode* curNextLev){
if(cur -> left == curNextLev && cur -> right != NULL){
return cur -> right;
}else{
while(cur -> next != NULL){
cur = cur -> next;
if(cur -> left != NULL && cur -> left != curNextLev) return cur -> left;
if(cur -> right != NULL && cur -> right != curNextLev) return cur -> right;
}
}
return NULL;
} TreeLinkNode* findStartNodeNextLev(TreeLinkNode* node){
if(NULL == node) return NULL;
if(node -> left != NULL) return node -> left;
return findNextNodeNextLev(node, node -> left);
}
};
最新文章
- 第一个PyQt程序
- block，inline和inline-block对比
- centos7.0 安装vsftp实录
- 使用自己的CSS框架（转）
- spring-boot 加载本地静态资源文件路径配置
- mac下 ssh免密码登陆设置
- sort 树 hash 排序
- Android实例-解决虚拟键盘遮挡问题(XE8+小米2)
- warning : json_decode(): option JSON_BIGINT_AS_STRING not implemented in xxx
- 初涉JavaScript模式 (4) : 构造函数
- HTML中的figure与figcaption标签
- oracle 修改dbid和dbname
- java 集合中将元素倒序排列
- 一张表搞懂各种 Docker 监控方案 - 每天5分钟玩转 Docker 容器技术（86）
- 机器学习-kNN
- 写的还不错的专题，android性能优化
- SVN汉化教程2017.10.6
- 使用docker安装sentry
- 配置中心Server端
- IIS7.0上传在大小限制