继续思考"填充每个节点指向最右节点的next指针" 这道题
如果给定的树可以是任意的二叉树呢?你之前的给出的算法还有效吗?
注意：
- 你只能使用常量的额外内存空间
例如：
给出的二叉树如下：
调用完你给出的函数之后，这棵树应该变成：
[编程题]填充每个节点指向最右节点的next指针 ii
核心思路：
如果当前层所有结点的next 指针已经设置好了，那么据此，下一层所有结点的next指针 也可以依次被设置。
class Solution
{
public:
void connect(TreeLinkNode *root)
{
while(root)
{
TreeLinkNode dummy(-1), *prev;
prev = &dummy;
for(auto p = root; p; p = p->next)
{
if(p->left)
{
prev->next = p->left;
prev = prev->next;
}
if(p->right)
{
prev->next = p->right;
prev = prev->next;
}
}
root = dummy.next; // 指向下一层的第一个节点
}
}
};
发表于 2016-08-10 22:01:03
回复(11)
public void connect(TreeLinkNode root) {
while (root != null) {
//tmpLevelFirst为新建立的每层第一个节点（为了方便后面遍历当前行节点）
TreeLinkNode tmpLevelFirst = new TreeLinkNode(0);
TreeLinkNode cur = tmpLevelFirst;
while (root != null) {
if (root.left != null) {
cur.next = root.left;
cur = cur.next;
}
if (root.right != null) {
cur.next = root.right;
cur = cur.next;
}
root = root.next;
}
root = tmpLevelFirst.next;
}
}
发表于 2017-08-09 10:35:14
回复(3)
看了下讨论区的代码，几乎都没达到常量内存空间的要求；
class Solution {
public:
void connect(TreeLinkNode *root) {
TreeLinkNode*cur = root;
TreeLinkNode*pre;
int count = 1;
while (cur){
bool flag = true;
for (auto p = cur; p; p = p->next){
if (p->left){
if (flag){
cur = p->left;
flag = false;
pre = p->left;
}
else{
pre->next = p->left;
pre = pre->next;
}
}
if (p->right){
if (flag){//第一次进入该层
cur = p->right;
flag = false;
pre = p->right;
}
else{
pre->next = p->right;
pre = pre->next;
}
}
}
if (flag)//如果没进入for循环说明cur已经是最后一层
return;
}
}
};
发表于 2018-05-27 20:58:16
回复(2)
class Solution {
public:
void connect(TreeLinkNode *root) {
//利用层序遍历思想，需要注意的是对每层的节点都进行处理
if(root==NULL) return;
queue<TreeLinkNode*> que;
que.push(root);
while(!que.empty()){
int n=que.size();
for(int i=0;i<n;i++){
TreeLinkNode* tmp=que.front();
que.pop();
if(tmp->left) que.push(tmp->left);
if(tmp->right) que.push(tmp->right);
if(i!=n-1) tmp->next=que.front();
else tmp->next=NULL;
}
}
}
};
这个问题我们可以通过二叉树的层序遍历进行解决，需要注意的是，对每一层的节点进行对应的层序遍历！
发表于 2017-12-12 22:08:52
回复(4)
所以告诉我为什么问题一和问题二我用同一份代码就都过了。。。
import java.util.LinkedList;
import java.util.Queue;
public class Solution {
public void connect(TreeLinkNode root) {
if(root == null)
return;
Queue<TreeLinkNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
int len = queue.size();
for(int i = 0; i < len; i++){
TreeLinkNode tmp = queue.poll();
if(i == len - 1){
tmp.next = null;
}else {
tmp.next = queue.peek();
}
if(tmp.left != null)
queue.offer(tmp.left);
if(tmp.right != null)
queue.offer(tmp.right);
}
}
}
}
发表于 2017-05-07 10:30:03
回复(8)
import java.util.*;
// 层次遍历,记录每一层的结点个数,循环设置next指针
public void connect(TreeLinkNode root) {
if(root == null) return;
Queue<TreeLinkNode> queue = new LinkedList<>();
queue.add(root);
int curCount = 1;
int nextCount = 0;
while ( ! queue.isEmpty()) {
TreeLinkNode[] arr = new TreeLinkNode[curCount]; // 存放一层结点
for (int i = 0; i < curCount; i ++) {
TreeLinkNode curNode = queue.poll();
arr[i] = curNode;
if(curNode.left != null) {
queue.add(curNode.left);
nextCount ++;
}
if(curNode.right != null) {
queue.add(curNode.right);
nextCount ++;
}
}
for (int i = 0; i < arr.length - 1; i ++) {
arr[i].next = arr[i + 1];
}
curCount = nextCount;
nextCount = 0;
}
}
编辑于 2017-03-19 22:27:33
回复(0)
class Solution {
public:
void connect(TreeLinkNode *root) {
if(root == NULL)
return;
//层次遍历
queue<TreeLinkNode*> q;
q.push(root);
TreeLinkNode* curNode = NULL;
TreeLinkNode* nextNode = NULL;
while(! q.empty()){
//和一般的层次遍历略有不同，每次while要把当前层的节点全部弹出去
int len = q.size();
curNode = q.front();
q.pop();
if(curNode->left != NULL)
q.push(curNode->left);
if(curNode->right != NULL)
q.push(curNode->right);
for(int i = 1;i<len;++i){
nextNode = q.front();
q.pop();
curNode->next = nextNode;
curNode = nextNode;
if(curNode->left != NULL)
q.push(curNode->left);
if(curNode->right != NULL)
q.push(curNode->right);
}
curNode->next = NULL;
}
}
};
发表于 2016-08-31 18:30:13
回复(0)
// Two Solutions
class Solution {
public:
// DFS
void connect(TreeLinkNode* root) {
int max_depth = -1;
vector<TreeLinkNode*> nexts;
function<void(TreeLinkNode*, int)> DFS =
[&](TreeLinkNode* r, int d) -> void {
if (!r) return;
if (d > max_depth) {
nexts.emplace_back(r);
max_depth = d;
} else {
r->next = nexts[d];
nexts[d] = r;
}
DFS(r->right, d + 1);
DFS(r->left, d + 1);
};
DFS(root, 0);
}
// BFS
void connectII(TreeLinkNode *root) {
// corner case
if (!root) return;
queue<TreeLinkNode*> q{{root}};
while (not q.empty()) {
size_t s = q.size();
TreeLinkNode* pre = nullptr;
while (s--) {
auto curr = q.front(); q.pop();
if (pre) pre->next = curr;
if (curr->left) q.emplace(curr->left);
if (curr->right) q.emplace(curr->right);
pre = curr;
}
}
}
};
发表于 2021-09-13 18:52:14
回复(0)
/**
* Definition for binary tree with next pointer.
* public class TreeLinkNode {
* int val;
* TreeLinkNode left, right, next;
* TreeLinkNode(int x) { val = x; }
* }
*/
public class Solution {
public void connect(TreeLinkNode root) {
while(root != null){
TreeLinkNode dummy = new TreeLinkNode(0);
TreeLinkNode cur = dummy;
while(root != null){
if(root.left != null){
cur.next = root.left;
cur = cur.next;
}
if(root.right != null){
cur.next = root.right;
cur = cur.next;
}
root = root.next;
}
root = dummy.next;
}
}
}
发表于 2020-10-06 10:15:25
回复(0)
leetcode原题提示：
- You may only use constant extra space.
- Recursive approach is fine, you may assume implicit stack space does not count as extra space for this problem.
/**
* Definition for binary tree with next pointer.
* public class TreeLinkNode {
* int val;
* TreeLinkNode left, right, next;
* TreeLinkNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeLinkNode connect(TreeLinkNode root) {
TreeLinkNode head = root;
while(head!=null){
// 递归构造每一层的链表：从最左边元素连到最右边元素
// 当前节点是当前层的最左边节点，返回的是子节点一层的最左边节点
head = findNext(head, head.next);
}
return root;
}
// 子节点的最右边元素，是父节点的右边元素的子节点的最左边元素
// 返回当前节点子节点的最左边元素
public TreeLinkNode findNext(TreeLinkNode node, TreeLinkNode pNext){
TreeLinkNode next = null;
if(pNext!=null) {
next = findNext(pNext, pNext.next);
}
if(node.right!=null){
node.right.next = next;
next = node.right;
}
if(node.left!=null){
node.left.next = next;
next = node.left;
}
return next;
}
}
编辑于 2020-01-11 11:46:49
回复(0)
class Solution {
public:
void connect(TreeLinkNode *root) {
if(!root)return;
queue<TreeLinkNode*>que;
que.push(root);
while(!que.empty()){
int len=que.size();
for(int i=0;i<len;i++){
TreeLinkNode* cur=que.front();
que.pop();
if(i!=len-1)
cur->next=que.front();
if(cur->left)que.push(cur->left);
if(cur->right)que.push(cur->right);
}
}
}
};
发表于 2019-08-20 18:14:27
回复(0)
和上一题基本上一样。
唯一的区别就是每一层的节点数不一样了。
把下一层的节点数统计出来。每次往队列中添加节点时，把计数器加一即可。
public class Solution {
public void connect(TreeLinkNode root) {
if (root == null) return;
int n = 1; //这一行的个数。
int row = 0; //行号。
int loc = 0; //当前位置。
int next = 0;
TreeLinkNode pre = null; //前一个节点。
Stack<TreeLinkNode> stack = new Stack<>();
Queue<TreeLinkNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
loc++;
TreeLinkNode node = queue.poll();
if (pre != null) pre.next = node;
if (node.left != null) {
queue.offer(node.left);
next++;
}
if (node.right != null) {
queue.offer(node.right);
next++;
}
if (loc == n) {
node.next = null;
row++;
n = next;
next = 0;
loc = 0;
pre = null;
} else {
pre = node;
}
}
}
}
发表于 2019-06-17 16:30:49
回复(0)
//常量空间 三个指针
class Solution {
public:
void connect(TreeLinkNode *root) {
TreeLinkNode *p = NULL, *cur = NULL, *f = root;
while(f){
p = f;
cur = NULL;
while(!cur && p){
if(p -> right && p -> left) {p -> left -> next = p -> right; cur = p -> right;}
else if(p -> left) cur = p -> left;
else if(p -> right) cur = p -> right;
p = p -> next;
}
while(p){
if(p -> right && p -> left) {
cur -> next = p -> left;
p -> left -> next = p -> right;
cur = p -> right;
}
else if(p -> left) {cur -> next = p -> left; cur = p -> left;}
else if(p -> right) {cur -> next = p -> right; cur = p -> right;}
p = p -> next;
}
while(f){
if(f -> left) {f = f -> left; break;}
else if (f -> right) {f = f -> right; break;}
f = f -> next;
}
}
return ;
}
};
发表于 2019-04-05 11:22:50
回复(0)
class Solution {
public:
void connect(TreeLinkNode *root) {
if(root == NULL)
{
return ;
}
TreeLinkNode *node1,*node2;
queue<TreeLinkNode*> que;
que.push(root);
int count = 0;
while(!que.empty())
{
count = que.size();
node1=que.front();
que.pop();
if(node1->left != NULL)
que.push(node1->left);
if(node1->right != NULL)
{
que.push(node1->right);
}
count--;
while(count-- > 0)
{
node2 = que.front();
que.pop();
if(node2->left != NULL)
que.push(node2->left);
if(node2->right != NULL)
que.push(node2->right);
node1->next = node2;
node1 = node2;
}
node1->next = NULL;
}
}
};
发表于 2018-08-20 17:32:36
回复(0)
/**
* 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) {
while(root){
TreeLinkNode temp(-1),*pre;
pre=&temp;
for(auto p=root;p;p=p->next){
if(p->left){
pre->next=p->left;
pre=pre->next;
}
if(p->right){
pre->next=p->right;
pre=pre->next;
}
}
root=temp.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) {
while(root){
TreeLinkNode temp(-1),*pre;
pre=&temp;
for(auto p=root;p;p=p->next){
if(p->left){
pre->next=p->left;
pre=pre->next;
}
if(p->right){
pre->next=p->right;
pre=pre->next;
}
}
root=temp.next;
}
}
};
发表于 2018-04-08 18:36:32
回复(0)
/**
* 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) {}
* };
public:
void connect(TreeLinkNode *root) {
if (!root)
return;
TreeLinkNode *p=root->next,*q=NULL;
while (p!=NULL){
if (p->left==NULL && p->right==NULL){
p=p->next;continue;
}
if (p->left!=NULL) {
q=p->left;
break;
}
if (p->right!=NULL) {
q=p->right;
break;
}
}
if (root->left&&root->right){
root->left->next=root->right;
root->right->next=q;
}
else if(root->left&&!root->right){
root->left->next=q;
}
else if(!root->left&&root->right){
root->right->next=q;
}
else
return;
connect(root->right);
connect(root->left);
}
};
* 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)
return;
TreeLinkNode *p=root->next,*q=NULL;
while (p!=NULL){
if (p->left==NULL && p->right==NULL){
p=p->next;continue;
}
if (p->left!=NULL) {
q=p->left;
break;
}
if (p->right!=NULL) {
q=p->right;
break;
}
}
if (root->left&&root->right){
root->left->next=root->right;
root->right->next=q;
}
else if(root->left&&!root->right){
root->left->next=q;
}
else if(!root->left&&root->right){
root->right->next=q;
}
else
return;
connect(root->right);
connect(root->left);
}
};
发表于 2018-01-23 20:44:23
回复(0)
//类似BFS的思想
class Solution {
public:
void connect(TreeLinkNode *root) {
while(root){
TreeLinkNode dummy(-1),*pre=&dummy;
while(root){
if(root->left) pre->next=root->left,pre=pre->next;
if(root->right) pre->next=root->right,pre=pre->next;
root=root->next;
}
root=dummy.next;
}
}
};
发表于 2017-08-20 19:26:53
回复(0)
class Solution {
public:
void connect(TreeLinkNode *root) {
while(root)
{
TreeLinkNode L(-1),*f,*p;
f = &L;
p = root;
while(p)
{
if(p->left != NULL)
{
f->next = p->left;
f = f->next;
}
if(p->right != NULL)
{
f->next = p->right;
f = f->next;
}
p = p->next;
}
root = L.next;
}
}
};
发表于 2017-08-17 01:25:45
回复(0)
/**
* Definition for binary tree with next pointer.
* public class TreeLinkNode {
* int val;
* TreeLinkNode left, right, next;
* TreeLinkNode(int x) { val = x; }
* }
*/
//层次遍历 记录每层的节点个数 并将一层元素存到一个临时数组中 遍历数组添加右指针
import java.util.*;
public class Solution {
public void connect(TreeLinkNode root) {
if(root == null){
return;
}
int cur=1;
int next=0;
LinkedList<TreeLinkNode> list=new LinkedList<TreeLinkNode>();
list.add(root);
while(!list.isEmpty()){
TreeLinkNode temp[]=new TreeLinkNode[cur];
for(int i=0;i<cur;i++){
temp[i]=list.poll();
if(temp[i].left!=null){
next++;
list.add(temp[i].left);
}
if(temp[i].right!=null){
next++;
list.add(temp[i].right);
}
}
for(int i=1;i<cur;i++){
temp[i-1].next=temp[i];
}
cur=next;
next=0;
}
}
}
发表于 2017-08-13 13:15:32
回复(0)
问题信息
难度：
97条回答
112收藏
28086浏览
通过挑战的用户
查看代码-
2022-09-14 11:11:02 -
2022-09-13 09:50:02 -
2022-09-12 17:11:27
-
2022-09-11 15:06:47 -
2022-08-20 14:25:19
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
