首页 > 试题广场 >

填充每个节点指向最右节点的next指针 ii

[编程题]填充每个节点指向最右节点的next指针 ii

热度指数：16162 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

继续思考"填充每个节点指向最右节点的next指针" 这道题

如果给定的树可以是任意的二叉树呢?你之前的给出的算法还有效吗?

注意：

你只能使用常量的额外内存空间

例如：

给出的二叉树如下：

调用完你给出的函数之后，这棵树应该变成：

说明：本题目包含复杂数据结构TreeLinkNode，点此查看相关信息

算法知识视频讲解

Java

刻苦的大熊猫在度假

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)

Java

LiberHome

/**
 * 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)

Java

iMi丶

    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)

Java

AriesLi

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)

Java

牛奶椰子糖

    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)

Java

七仔0312

层序遍历

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)

Java

洁白

//渣渣一个。。抄的别人的 自己想了很久才想明白
//移动一个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)

Java

萨仁朝格图（大家去脉脉沟通）

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)

Java

阿拉要洗澡

/**

* 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)

Java

pp11

/**
 * 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)

Java

丫丁

//层序遍历的思想做这道理思路应该是很清晰简单的。
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)

Java

詆調壹點

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)

Java

油头教授的坩埚

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)

Java

城市里的养猫者

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;
        }
        
    }
}