【题目】
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
【分析】
无
【代码】
/*********************************
* 日期:2014-12-24
* 作者:SJF0115
* 题目: 117.Populating Next Right Pointers in Each Node II
* 来源:https://oj.leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/
* 结果: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);
}
分享到:
相关推荐
用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现Leetcode题目.zip用C语言实现...
JVM 基础 JAVA 并发 JVM 性能调优 LeetCode 算法 .......
My Solutions to Leetcode Database problems. 我的 Leetcode 数据.zip
原创:leetcode 107. 二叉树的层次遍历 II【队列】* Definition for a binary tree node.
Leetcode 题解.pdf
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...
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101.zip
LeetCode 后端.zip
原创:leetcode 111. 二叉树的最小深度记住:最小深度和最大深度方法不同。* Definition for a binary tree node.in
Leetcode101.zip
刷leetcode总结.md
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 ...
Leetcode 92. 反转链表 II问题描述算法解法1: 递归图示解法1:实现def reverseBetween(self, head: ListNode