Question:
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
Anwser 1:
/**
* 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) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(NULL == root){
return;
}
TreeLinkNode *cur = root->next;
TreeLinkNode *p = NULL;
while(cur != NULL){ // find last right node (left or right)
if(cur->left) {
p = cur->left;
break;
}
if(cur->right){
p = cur->right;
break;
}
cur = cur->next;
}
if(root->right){
root->right->next = p;
}
if(root->left){
root->left->next = root->right ? root->right : p;
}
connect(root->right); // from right to left
connect(root->left);
}
};
注意点:
1) list为非完美二叉树,右分支可能为空,因此从right -> left 遍历
2) 从最右分支开始查找,且root没有 left 节点,则找 right 节点
Anwser 2:
/**
* 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) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(NULL == root){
return;
}
queue<TreeLinkNode *> Q; // save one line root(s)
queue<TreeLinkNode *> Q2; // save next one line root(s), swap with Q
Q.push(root);
while(!Q.empty()){
TreeLinkNode *tmp = Q.front();
Q.pop();
if(tmp->left) Q2.push(tmp->left);
if(tmp->right) Q2.push(tmp->right);
if(Q.empty()){
tmp->next = NULL;
queue<TreeLinkNode*> tmpQ = Q; // swap queue
Q = Q2;
Q2 = tmpQ;
} else {
tmp->next = Q.front();
}
}
}
};
注意点:
1) 新增一个Q2队列,保存下一行的全部元素,辅助判断是最后一个元素(Q为空)则置为NULL
2) queue队列实现比递归要好
Anwser 3:
/**
* 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) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(NULL == root){
return;
}
queue<TreeLinkNode *> Q; // save one line root(s)
Q.push(root);
Q.push(NULL); // flag
while(!Q.empty()){
TreeLinkNode *tmp = Q.front();
Q.pop();
if(tmp != NULL){ // check flag
if(tmp->left) Q.push(tmp->left);
if(tmp->right) Q.push(tmp->right);
tmp->next = Q.front();
} else {
if(Q.empty()){ // pop flag = NULL, then check is empty
break;
}
Q.push(NULL);
}
}
}
};
注意点:
对比第二种方法,改进点是每一行结束处,采用NULL作为标志位
分享到:
相关推荐
leetcode卡 leetcode_python 项目介绍 想学学python,刷刷leetcode 打卡轨迹 2020-01-13 70 爬楼梯 2020-01-14 120 Triangle 2020-01-15 213 House Robberll -变种 198 337 2020-01-16 139 单词拆分 2020-01-20 104 ...
leetcode题库 pyshua Python 算法题练习 用法: python Judge.py library problem 例子: python Judge.py leetcode TwoSum 如何贡献: 收录题库 LeetCode (还有4题未录入, 分别为 LRU Cache, Copy List with Random ...
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...
Populating Next Right Pointers in Each Node II 二叉树的构建 Construct Binary Tree from Preorder and Inorder Traversal Construct Binary Tree from Inorder and Postorder Traversal 二叉查找树 Unique ...
LeetCode题目Largest Rectangle in Histogram 解答
[117]填充每个节点的下一个右侧节点指针 II|populating-next-right-pointers-in-each-node-ii给定一个二叉树填充
leetcode-pp-node 官网后端。 使用 koa2 结合 Github Actions 开发。目前采用静态 JSON 存放题解,讲义,用户信息等数据,后期使用数据库承载内容。 TODOS 在 91 网站直接提交代码到力扣中,获取执行结果并在 91 中...
LeetCode 解决VS Code中的LeetCode问题 英文文件| 文件 :exclamation_mark: 注意 :exclamation_mark: -登录LeetCode端点的解决方法注意:如果使用的是leetcode-cn.com ,则可以忽略此部分。 最近,我们发现。 此问题...
lru cache leetcode leetcode 记录自己刷leetcode时遇到的一些值得记下来的题目, 分为一些子项 bytedance ...populating-next-right-pointers-in-each-node sum-root-to-leaf-numbers best-time-to-buy
421 | [Maximum XOR of Two Numbers in an Array](https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/) | [C++](./C++/maximum-xor-of-two-numbers-in-an-array.cpp) [Python](./Python/...
leetcode 两分球-2 问题1 () 问题2 () 问题3 ()
leetcode 两分球-1 问题1 () 问题2 () 问题3 ()
450._Delete_Node_in_a_BST【LeetCode单题讲解系列】
刷LeetCode刷LeetCode刷LeetCode刷LeetCode刷LeetCode
leetcode 答案解析 golang解答
一:题意: 删除一颗二叉搜索树的一个节点。 二:思路 二叉搜索树的结点删除比插入较为复杂,总体来说,结点的删除可归结为三种情况: 1、 如果结点z没有孩子... def deleteNode(self, root, key): def postOrder(r
蓄水池算法 leetcode leetcode Post: 《双指针的魅力》 《常见面试题思想方法整理》 ...populating-next-right-pointers-in-each-node-ii: 二级指针代码虽然简洁优雅,但是对性能有影响,不如一级指针加if else判断快。
Array题型_双指针Two_Pointers套路【LeetCode刷题套路教程2】
原创:leetcode 107. 二叉树的层次遍历 II【队列】* Definition for a binary tree node.
四平方和定理 leetcode Leetcode practice Table of content Tree 92.reverse-linked-list-ii (反转链表 II) 94.binary-tree-in...116.populating-next-right-pointers-in-each-node (填充每个节点的下一个右侧节点