继续思考"填充每个节点指向最右节点的next指针" 这道题
如果给定的树可以是任意的二叉树呢?你之前的给出的算法还有效吗?
注意：
- 你只能使用常量的额外内存空间
例如：
给出的二叉树如下：
调用完你给出的函数之后，这棵树应该变成：
[编程题]填充每个节点指向最右节点的next指针 ii
Java 76%
import java.util.*;
public class Solution {
public void connect(TreeLinkNode root) {
// 使用层序遍历，让每个节点的next指针指向右侧节点
if(root == null) return ;
Deque<TreeLinkNode> queue = new LinkedList<TreeLinkNode>();
queue.add(root);
while(!queue.isEmpty()){
int curSize = queue.size();
for(int i=0;i<curSize;i++){
TreeLinkNode curNode = queue.poll();
if(i == curSize-1){ // 该层最后一个元素
curNode.next = null;
}else{
curNode.next = queue.peek();
}
if(curNode.left != null) queue.add(curNode.left);
if(curNode.right != null) queue.add(curNode.right);
}
}
return ;
}
}
发表于 2021-10-11 15:40:12
回复(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)
public void connect(TreeLinkNode root) {
if(root == null){
return;
}
if(root.left == null && root.right == null){
return;
}
//用于标记每层第一个节点
TreeLinkNode firstOfEachRow = root;
//仍存在层未遍历
while(firstOfEachRow != null){
//用于标记上一个被连接节点
TreeLinkNode preNode = new TreeLinkNode(0);
//被连接节点的父节点
TreeLinkNode curNode = firstOfEachRow;
//下一层节点数量，用于实现首节点标记
int count = 0;
//下一层首节点
TreeLinkNode nextHead = null;
//未到当前层尾部
while(curNode != null){
//连接左节点
if(curNode.left != null){
//标记下一层第一个节点
if(count == 0){
nextHead = curNode.left;
count++;
}
//连接
preNode.next = curNode.left;
preNode = curNode.left;
}
//连接右节点
if(curNode.right != null){
//标记下一层第一个节点
if(count == 0){
nextHead = curNode.right;
count++;
}
//连接
preNode.next = curNode.right;
preNode = curNode.right;
}
curNode = curNode.next;
}
//转到下一层第一个节点
firstOfEachRow = nextHead;
}
}
发表于 2020-07-20 12:18:28
回复(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)
public void connect(TreeLinkNode root) {
TreeLinkNode curLevel=null;
TreeLinkNode nextLevel=root;
boolean hasNextLevel=true;
//当还有下一层时
while(hasNextLevel)
{
hasNextLevel=false;
curLevel=nextLevel;
while(curLevel!=null)
{
TreeLinkNode curNode=curLevel;
//左右孩子节点均不为空
if(curNode.left!=null&&curNode.right!=null)
{
//记录下一层起始位置
if(!hasNextLevel)
{
nextLevel=curNode.left;
hasNextLevel=true;
}
//左右孩子节点
curNode.left.next=curNode.right;
curLevel=curLevel.next;
//堂兄弟节点
while(curLevel!=null)
{
if(curLevel.left!=null)
{
curNode.right.next=curLevel.left;
break;
}
else if(curLevel.right!=null)
{
curNode.right.next=curLevel.right;
break;
}
//下一个
curLevel=curLevel.next;
}
}
//左孩子不空
else if(curLevel.left!=null)
{
//记录下一层起始位置
if(!hasNextLevel)
{
nextLevel=curNode.left;
hasNextLevel=true;
}
curLevel=curLevel.next;
//堂兄弟节点
while(curLevel!=null)
{
if(curLevel.left!=null)
{
curNode.left.next=curLevel.left;
break;
}
else if(curLevel.right!=null)
{
curNode.left.next=curLevel.right;
break;
}
//下一个
curLevel=curLevel.next;
}
}
//右孩子不空
else if(curLevel.right!=null)
{
//记录下一层起始位置
if(!hasNextLevel)
{
nextLevel=curNode.right;
hasNextLevel=true;
}
curLevel=curLevel.next;
//堂兄弟节点
while(curLevel!=null)
{
if(curLevel.left!=null)
{
curNode.right.next=curLevel.left;
break;
}
else if(curLevel.right!=null)
{
curNode.right.next=curLevel.right;
break;
}
//下一个
curLevel=curLevel.next;
}
}
else
{
curLevel=curLevel.next;
}
}
}
}
发表于 2019-03-20 17:35:11
回复(0)
层序遍历
public class Solution {
public void connect(TreeLinkNode root) {
if (root == null)
return;
TreeLinkNode dummy = new TreeLinkNode(-1);
TreeLinkNode cur;
TreeLinkNode prev = dummy;
for (cur = root; cur != null; cur = cur.next) {
if (cur.left != null) {
prev.next = cur.left;
prev = prev.next;
}
if (cur.right != null) {
prev.next = cur.right;
prev = prev.next;
}
}
connect(dummy.next);
}
}
发表于 2018-03-16 10:26:51
回复(0)
//渣渣一个。。抄的别人的 自己想了很久才想明白
//移动一个cur指针，来完成在当前层上的next指针赋值，
//如果像1一样，因为不是满二叉树，直接想通过判断left或者rigth是否为空，
//来赋值，那样判断特别多。
//用一个指针来记录当前层的第一个节点
public class Solution {
public void connect(TreeLinkNode root) {
if(root==null){
return ;
}
while(root!=null){
TreeLinkNode templevelfirst=new TreeLinkNode(0);//记录当前层的第一个节点
TreeLinkNode cur=templevelfirst;//负责移动的指针，cur和root不是在一层，cur移动在root的下一层，这个是更核心，记录当前层的第一个节点的指针
//在一中也用到了，（是p）
while(root!=null){
if(root.left!=null){
cur.next=root.left;//在第一次循环时，给templevelfirst的next赋值了，记录的就是当前层的第一个节点
cur=cur.next;
}
if(root.right!=null){
cur.next=root.right;
cur=cur.next;
}
root=root.next;//遍历这一层，向右移动
}
root=templevelfirst.next;//向下移动
}
}
}
编辑于 2017-12-20 21:12:28
回复(0)
import java.util.ArrayList;
public class Solution {
public void connect(TreeLinkNode root) {
if(root == null)return;
ArrayList<ArrayList<TreeLinkNode>> db = new ArrayList<ArrayList<TreeLinkNode>>();
ArrayList<TreeLinkNode> dbs;
dbs = new ArrayList<TreeLinkNode>();
dbs.add(root);
db.add(dbs);
int a=0;
while(dbs != null && dbs.size() != 0){
dbs = new ArrayList<TreeLinkNode>();
for(int i = 0; i < db.get(a).size(); i ++){
if(db.get(a).get(i).left != null)
dbs.add(db.get(a).get(i).left);
if(db.get(a).get(i).right != null)
dbs.add(db.get(a).get(i).right);
}
a ++;
if(dbs.size() != 0)
db.add(dbs);
}
for(int i = 0; i < db.size(); i ++){
for(int j = 0; j < db.get(i).size(); j ++){
if(j == db.get(i).size() - 1)
db.get(i).get(j).next = null;
else
db.get(i).get(j).next = db.get(i).get(j + 1);
}
}
}
}
发表于 2017-08-15 13:08:21
回复(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)
/**
* 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;
LinkedList<TreeLinkNode> queue = new LinkedList<TreeLinkNode>();
queue.offer(root);
int size = 0;
TreeLinkNode p = null;
TreeLinkNode q = null;
while (!queue.isEmpty()) {
size = queue.size();
for (int i = 0; i < size; ++i) {
q = queue.poll();
if (i != 0) {
p.next = q;
}
if (i == size - 1) {
q.next = null;
}
p = q;
if (q.left != null)
queue.offer(q.left);
if (q.right != null)
queue.offer(q.right);
}
}
return;
}
}
发表于 2017-07-31 22:45:53
回复(0)
//层序遍历的思想做这道理思路应该是很清晰简单的。
public void connect(TreeLinkNode root) {
Queue<TreeLinkNode> queue=new LinkedList<>();
if(root==null) return ;
queue.add(root);
while(!queue.isEmpty()){
int layerSize=queue.size();
while(layerSize--!=0){
TreeLinkNode node=queue.poll();
if(layerSize!=0) node.next=queue.peek();
else node.next=null;
if(node.left!=null) queue.add(node.left);
if(node.right!=null) queue.add(node.right);
}
}
}
编辑于 2017-04-29 14:59:08
回复(0)
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)
public class Solution { public void connect(TreeLinkNode root) { while(root != null){ TreeLinkNode tempChild = new TreeLinkNode(0); TreeLinkNode currentChild = tempChild; while(root!=null){ if(root.left != null) { currentChild.next = root.left; currentChild = currentChild.next;} if(root.right != null) { currentChild.next = root.right; currentChild = currentChild.next;} root = root.next; } root = tempChild.next; } } }
发表于 2017-03-11 23:31:14
回复(0)
public class Solution { //based on level order traversal public void connect(TreeLinkNode root) { TreeLinkNode head = null; //head of the next level TreeLinkNode prev = null; //the leading node on the next level TreeLinkNode cur = root; //current node of current level while (cur != null) { while (cur != null) { //iterate on the current level //left child if (cur.left != null) { if (prev != null) { prev.next = cur.left; } else { head = cur.left; } prev = cur.left; } //right child if (cur.right != null) { if (prev != null) { prev.next = cur.right; } else { head = cur.right; } prev = cur.right; } //move to next node cur = cur.next; } //move to next level cur = head; head = null; prev = null; } } }
发表于 2017-03-11 23:30:34
回复(0)
问题信息
难度：
15条回答
111收藏
26523浏览
通过挑战的用户
查看代码-
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群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
