【题目】
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 toNULL
.
Initially, all next pointers are set toNULL
.
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
Show Tags
【分析】
在层次遍历过程中,修改next指针指向。
类似于: [LeetCode]Binary Tree Level Order Traversal
【代码】
/*********************************
* 日期:2014-12-24
* 作者:SJF0115
* 题目: 116.Populating Next Right Pointers in Each Node
* 来源:https://oj.leetcode.com/problems/populating-next-right-pointers-in-each-node/
* 结果:AC
* 来源:LeetCode
* 总结:
**********************************/
#include <iostream>
#include <queue>
using namespace std;
struct TreeLinkNode {
int val;
TreeLinkNode *left;
TreeLinkNode *right;
TreeLinkNode *next;
TreeLinkNode(int x):val(x),left(NULL),right(NULL),next(NULL){}
};
class Solution {
public:
void connect(TreeLinkNode *root) {
if(root == NULL){
return;
}//if
queue<TreeLinkNode*> cur;
queue<TreeLinkNode*> next;
cur.push(root);
TreeLinkNode *p,*pre;
while(!cur.empty()){
pre = NULL;
// 当前层遍历
while(!cur.empty()){
// 出队列
p = cur.front();
cur.pop();
// 横向连接
if(pre != NULL){
pre->next = p;
}//if
pre = p;
// next保存下一层节点
// 左子树不空加入队列
if(p->left){
next.push(p->left);
}//if
// 右子树不空加入队列
if(p->right){
next.push(p->right);
}//if
}//while
p->next = NULL;
swap(next,cur);
}//while
}
};
//按先序序列创建二叉树
int CreateBTree(TreeLinkNode*& T){
int data;
//按先序次序输入二叉树中结点的值,-1表示空树
cin>>data;
if(data == -1){
T = NULL;
}
else{
T = new TreeLinkNode(data);
//构造左子树
CreateBTree(T->left);
//构造右子树
CreateBTree(T->right);
}
return 0;
}
// 输出
void LevelOrder(TreeLinkNode *root){
if(root == NULL){
return;
}//if
TreeLinkNode *p = root,*q;
while(p){
q = p;
// 横向输出
while(q){
cout<<q->val<<"->";
q = q->next;
}//while
if(q == NULL){
cout<<"NULL"<<endl;
}//if
p = p->left;
}//while
}
int main() {
Solution solution;
TreeLinkNode* root(0);
CreateBTree(root);
solution.connect(root);
LevelOrder(root);
}
【分析二】
对于一个左节点,相邻节点为父节点的右子节点。next指针指向父节点的右子节点。
对于一个当右节点稍微麻烦一些。相邻节点为父节点的右相邻节点的左子结点。父节点的右相邻节点还可能为空,所以需要判断一下。
// 父节点右相邻节点不为空
if(next){
connect(cur->right,next->left);
}//if
// 父节点右相邻节点为空
else{
connect(cur->right,NULL);
}//else
next指针指向父节点的右相邻节点的左子结点或者空指针。
【代码二】
class Solution {
public:
void connect(TreeLinkNode *root) {
if(root == NULL){
return;
}//if
connect(root,NULL);
}//void
private:
// cur 当前节点 next 右相邻节点
void connect(TreeLinkNode *cur,TreeLinkNode *next) {
if(cur == NULL){
return;
}//if
else{
cur->next = next;
}//else
// 左子树(连接的下一节点为父节点的右节点)
if(cur->left){
connect(cur->left,cur->right);
}//if
// 右子树(连接的下一节点为父节点相邻节点的左节点)
if(cur->right){
// 右相邻节点不为空
if(next){
connect(cur->right,next->left);
}//if
// 右相邻节点为空
else{
connect(cur->right,NULL);
}//else
}//if
}//void
};
分享到:
相关推荐
用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现...
lru缓存leetcode leetcode 大批 41. First Missing Positive 广度优先搜索 773. Sliding Puzzle 864. Shortest Path to Get All Keys 深度优先搜索 996. Number of Squareful Arrays 拓扑排序 269. Alien Dictionary...
JVM 基础 JAVA 并发 JVM 性能调优 LeetCode 算法 .......
My Solutions to Leetcode Database problems. 我的 Leetcode 数据.zip
Leetcode 题解.pdf
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101.zip
LeetCode 后端.zip
原创:leetcode 111. 二叉树的最小深度记住:最小深度和最大深度方法不同。* Definition for a binary tree node.in
Leetcode101.zip
刷leetcode总结.md
原创:leetcode 107. 二叉树的层次遍历 II【队列】* Definition for a binary tree node.
Recording personal Java, Python, JavaScript solutions for Leetcode problems. 记录个人 Java, Python, JavaScript 的Leetcode题解.zip
原创:leetcode 5. 最长回文子串//寻找以i-1,i为中点偶数长度的回文//寻找以i为中心的奇数长度的回文。
My Solutions to Leetcode problems. All solutions support C
原创:leetcode 22.括号生成【回溯】对待这种问题,千万别暴力搜索,那样太笨了。但是这个方法是最容易理解的//回溯法 (后面的括号) 不可以大于 (前面
leetcode-editor,在ide中做leetcode练习,支持leetcode.com和leetcode-cn.com,以满足练习的基本需求。理论上支持:intellij idea phpstorm webstorm pycharm rubymine appcode clion goland datagrip rider mps ...
LeetCode674. 最长连续递增序列674. 最长连续递增序列解题思路:记录每次递增序列的长度,max存储最大长度// 递增序列更新最大长度} else
LeetCode746.使用最小花费爬楼梯746. 使用最小花费爬楼梯解题思路:动态规划当前楼梯最小值=Math.min(前一步最小值,前两步最小值)简化 mi