首页 > 试题广场 >

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

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

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

给定一个二叉树

    struct TreeLinkNode {
        TreeLinkNode *left;
        TreeLinkNode *right;
        TreeLinkNode *next;
    }

填充所有节点的next指针，指向最接近它的同一层右边节点。如果没有同一层没有右边的节点，则应该将next指针设置为NULL。

初始时，所有的next指针都为NULL

注意：

你只能使用常量级的额外内存空间
可以假设给出的二叉树是一个完美的二叉树(即，所有叶子节点都位于同一层，而且每个父节点都有两个孩子节点)。

例如：给出如下的完美二叉树

调用完你给出的函数以后，这颗二叉树应该变成：

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

算法知识视频讲解

Java

牛客208400313号

Java6行搞定

public class Solution {
    public void connect(TreeLinkNode root) {
        if (root == null || root.left == null) return;

        root.left.next = root.right;
        if (root.next != null) 
            root.right.next = root.next.left;

        connect(root.left);
        connect(root.right);
    }
}

发表于 2022-09-07 12:01:23 回复(0)

Java

花落梦里

import java.util.*;
public class Solution {
    Queue<TreeLinkNode> queue = new LinkedList<>();
    TreeLinkNode node,preNode =null;
    int count=1;
    int n=1;
    public void connect(TreeLinkNode root) {
       if(root==null) return;
        queue.offer(root);
       while(!queue.isEmpty()){
           node=queue.poll();
           if(count==n){//2的幂次方,则上一个指向null
                if(preNode!=null){
                   preNode.next=null;
                }
               n=n*2;
           }
           else{
               preNode.next=node;//横向指针
           }
            
           if(node.left!=null){
               queue.offer(node.left);
               queue.offer(node.right);
           }
        preNode=node;
        count++;
       }
    }  
        
    }

发表于 2021-01-02 19:55:49 回复(0)

Java

liangshang

首先是空间复杂度为O(n)的解法，使用队列的层次遍历：

import java.util.*;
public class Solution {
    public void connect(TreeLinkNode root) {
        if (root == null) return;
        Queue<TreeLinkNode> queue = new LinkedList<>(); 
        queue.add(root);
        while (!queue.isEmpty()) {
            int n = queue.size();
            for (int i = 0; i < n; ++i) {
                TreeLinkNode node = queue.poll();
                if (i < n - 1) {
                    node.next = queue.peek();
                }
                if (node.left != null)
                    queue.offer(node.left);
                if (node.right != null) 
                    queue.offer(node.right);
            }
        }
    }
}

然后是空间复杂度为O(1)的解法，核心思想是在当前层遍历并完成下一层的节点之间的连接：

import java.util.*;
public class Solution {
    public void connect(TreeLinkNode root) {
        if (root == null) return;
        TreeLinkNode leftmost = root;
        while (leftmost.left != null) {
            //leftmost是每一层的第一个节点
            TreeLinkNode head = leftmost;
            //在同一层中从左向右遍历
            while (head != null) {
                //首先在该结点的左孩子和右孩子连接起来
                head.left.next = head.right;
                //再把该节点的右孩子同该节点的右测节点的左孩子连接起来
                if (head.next != null) {
                    head.right.next = head.next.left;
                }
                //从左向右遍历
                head = head.next;
            }
            //当前层遍历完成后转移到下一层
            leftmost = leftmost.left;
        }
    }
}

发表于 2020-10-21 21:09:19 回复(0)

Java

就是很菜

package LeetCode;
import java.util.*;
 class TreeLinkNode {
      int val;
      TreeLinkNode left, right, next;
      TreeLinkNode(int x) { val = x; }
   }
 
public class Solution {
    public void connect(TreeLinkNode root) {
        if(root==null)
        	return ;
        Queue<TreeLinkNode> queue = new LinkedList<>();
        queue.add(root);
        int size= queue.size();
        while(!queue.isEmpty()) {
        	TreeLinkNode node = queue.remove();
        	size--;
        	if(node.left!=null) {
        		queue.add(node.left);
        	}
        	if(node.right!=null) {
        		queue.add(node.right);
        	}
        	if(size==0) {
        		node.next=null;
        		size=queue.size();
        	}else {
        		node.next=queue.peek();
        	}
        }
    }
}

发表于 2020-04-25 13:44:15 回复(0)

Java

追梦赤子心2019

这道题可以使用层次遍历的思想解决。
import java.util.*;
public class Solution {
    public void connect(TreeLinkNode root) {
        Queue<TreeLinkNode> queue = new LinkedList<TreeLinkNode>();
        if(root != null){
            root.next = null;
            queue.add(root);
        }
        TreeLinkNode node = null;
        while(queue.size() > 0){
            int size = queue.size();
            for(int i = 0; i < size; i++){
                node = queue.poll();
                if(i == size - 1){
                    node.next = null;
                }else{
                    node.next = queue.peek();
                }
                if(node.left != null){
                    queue.add(node.left);
                }
                if(node.right != null){
                    queue.add(node.right);
                }
            }
        }
    }
}

发表于 2020-04-21 15:52:57 回复(0)

Java

悟Kong

public class Solution {
    public void connect(TreeLinkNode root) {
        if(root==null)
            return;
        TreeLinkNode p=root;
        TreeLinkNode q=new TreeLinkNode(0);
        while(p.left!=null){
            q=p;
            while(q!=null){
                q.left.next=q.right;
                if(q.next!=null)
                    q.right.next=q.next.left;
                q=q.next;
            }
            p=p.left;
        }
        return;
    }
}

发表于 2020-03-02 21:01:30 回复(0)

Java

key、L

我好菜啊。。。每次都是看过别人的代码才能理解思路，本题很类似用非递归法求解二叉树的最大深度(maximum-depth-of-binary-tree)，就是用一个辅助的队列，只让每一层的最后一个节点的next = null，二叉树每层节点依次入队，然后每次出队元素的 next 指向队顶的元素🤐

/**
 * Definition for binary tree with next pointer.
 * public class TreeLinkNode {
 *     int val;
 *     TreeLinkNode left, right, next;
 *     TreeLinkNode(int x) { val = x; }
 * }
 */
import java.util.LinkedList;
import java.util.Queue;
public class Solution {
    public void connect(TreeLinkNode root) {
        if(root == null)
            return ;
        //思路：注意到二叉树的每一层只有最后一个节点的next指向null。
        //因此联想到二叉树的层次遍历，用队列保存每一层的节点，每层除了最后一个节点
        //其他的节点的next均指向下一个节点
        Queue<TreeLinkNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty())
        {
            int length = queue.size();
            for(int i = 0; i < length; i++)
            {
                TreeLinkNode linkNode = queue.poll();
                if(i == length -1)
                    linkNode.next = null;
                else
                {
                    linkNode.next = queue.peek();
                }
                if(linkNode.left != null)
                    queue.offer(linkNode.left);
                if(linkNode.right != null)
                    queue.offer(linkNode.right);
            }
        }
    }
}

发表于 2020-01-08 10:56:56 回复(0)

Java

whynotybb

//层次遍历
public void connect(TreeLinkNode root) {
    if (root==null)
        return;
    LinkedList<TreeLinkNode> queue=new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()){
        int size=queue.size();
        for (int i=0;i<size;i++){
            TreeLinkNode node= queue.removeFirst();
            if (i+1<size)
                 node.next= queue.get(0);;
            if (node.left!=null)
                queue.add(node.left);
            if (node.right!=null)
                queue.add(node.right);
        }
    }
}

发表于 2019-07-22 15:40:00 回复(0)

Java

给菜鸡一个offer吧

public class Solution {
public void connect(TreeLinkNode root) {
if(root==null) return;
TreeLinkNode pre = null , first = null, cur = root;

while(cur!=null){
while(cur!=null&&(cur.left==null&&cur.right==null)){
cur = cur.next;
}
if(cur==null) return;
pre = first = cur.left==null?cur.right:cur.left;
while(cur!=null){
if(cur.left!=null){
pre.next = cur.left;
pre = pre.next;
}
if(cur.right!=null){
pre.next = cur.right;
pre = pre.next;
}
cur = cur.next;
}
pre.next = null;
cur = first;
}

}
}

发表于 2019-05-29 16:06:28 回复(0)

Java

jax_

/**
* 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) {
if(root == null)
return ;
root.next =null;
dfs(root);

}
public void dfs(TreeLinkNode a)
{
while(a.left != null && a.right != null)
{
a.left.next = a.right;
if(a.next == null)
a.right.next = null;
else
a.right.next = a.next.left;
dfs(a.left);
dfs(a.right);
return;
}

}
}

发表于 2019-03-13 13:43:06 回复(0)

Java

Tbiubiu

总体思路就是使用层序遍历，自己制定规则判断是否同一层，具体规则自己定，有人用长度（利用了完美二叉树的性质），这里用的是自己创建的KV对，通过判断队列中下一个节点是否是同一层


	public static class TreeLinkNode{ 



	int val;



	TreeLinkNode left;



	TreeLinkNode right;



	TreeLinkNode next;



	public TreeLinkNode(int val) {



	 // TODO Auto-generated constructor stub



	this.val = val;



	}



	}



	





	public static class TreeLinkNodeOrder{



	TreeLinkNode node;



	 int order; 



	public TreeLinkNodeOrder(TreeLinkNode node, int order) {



	 // TODO Auto-generated constructor stub



	this.node = node;



	this.order = order;



	}



	}



	public static void connect(TreeLinkNode root) {



	if (root == null) {



	 return; 



	}



	Queue<TreeLinkNodeOrder> queue = new LinkedList<>();



	queue.add(new TreeLinkNodeOrder(root, 1));



	while (!queue.isEmpty()) {



	TreeLinkNodeOrder tmp = queue.poll();



	TreeLinkNode node = tmp.node;



	int order = tmp.order;



	if (!queue.isEmpty() && order == queue.peek().order) {



	node.next = queue.peek().node;



	} else {



	node.next = null;



	}



	if (node.left != null) {



	queue.add(new TreeLinkNodeOrder(node.left, order+1));



	}



	if (node.right != null) {



	queue.add(new TreeLinkNodeOrder(node.right, order+1));



	}



	}



	 }

编辑于 2019-02-28 11:53:02 回复(0)

Java

想做个咸鱼

本题从题意来说，最好的方法是使用BFS，涉及到BSF就要维护一个o(n)的空间复杂度，本题作者希望能够使用TreeLinkNode下扩展的next实现BFS搜索的功能，从而不需要维护大空间，仅使用常数空间就能实现。思路是，建立next的同时，做层次遍历，直到null为止，然后将变量跳到下一个阶层的最左节点，在边建立边层次，直到这个过程彻底结束

public class Solution {
    public void connect(TreeLinkNode root) {
        if(root==null)return;
        while(root.left!=null){
            TreeLinkNode node=root;
            while(node!=null){
                node.left.next=node.right;
                if(node.next!=null)node.right.next=node.next.left;
                node=node.next;
            }
            root=root.left;
        }
    }
}

发表于 2018-12-27 19:18:25 回复(5)

Java

回去等通知吧

//按行打印二叉树+一个栈
public static void connect(TreeLinkNode root) {
        LinkedList<TreeLinkNode> linkedList = new LinkedList();
        Stack<TreeLinkNode> s = new Stack<>();
        if (root == null) {
            return;
        }
        linkedList.add(root);
        TreeLinkNode next = null;
        TreeLinkNode cur = null;
        int start = 0;
        int end = 1;
        while (!linkedList.isEmpty()) {
            TreeLinkNode temp = linkedList.pollFirst();
            s.push(temp);
            start++;
            if (temp.left != null) {
                linkedList.add(temp.left);
            }
            if (temp.right != null) {
                linkedList.add(temp.right);
            }
            if (start == end){
                while (!s.isEmpty()){
                    cur = s.pop();
                    cur.next = next;
                    next = cur;
                }
                next = null;
                start = 0;
                end = linkedList.size();
            }
        }
    }

发表于 2018-07-23 09:53:44 回复(0)

Java

七仔0312

public class Solution {
    public void connect(TreeLinkNode root) {
        if (root == null)
            return;
        if (root.left == null && root.right == null)
            return;
        else if (root.left == null)
            connect(root.right);
        else if (root.right == null)
            connect(root.left);
        else {
            root.left.next = root.right;
        }
        if (root.next != null && root.right != null) {
            root.right.next = root.next.left;
        }
        connect(root.left);
        connect(root.right);
    }
}

发表于 2018-03-16 09:57:29 回复(0)

Java

木梳子

public class Solution {
public void connect(TreeLinkNode root) {
if(root == null || root.left == null && root.right == null)    return;    //空树或者单节点树不需要额外的处理

//多节点树
//定义cur，用于遍历树的具体某一层的节点；定义first，永远表示当前层的下一层的首个节点
TreeLinkNode cur = root, first = root;

//每次遍历完当前层的结果是当前层的下一层的节点的next指针全部归位，因此，当first是叶子节点的时候说明已经全部处理完毕
while(first.left != null && first.right != null){
//实现当前层到下一层之间的递推
cur = first;    //每层的处理从当前层的第一个节点开始
first = cur.left;    //first始终指向当前层的下一层的首个节点
while(cur != null){
if(cur.left != null)
cur.left.next = cur.right;
if(cur.right != null && cur.next != null)
cur.right.next = cur.next.left;

cur = cur.next;    //同一层之间的递推
}
}
}
}

发表于 2017-10-31 21:49:54 回复(0)

Java

阿拉要洗澡

/**

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

if(root == null){

return;

}

if(root.left!=null && root.right!=null){

root.left.next=root.right;

}

if(root.next!=null && root.right!=null){

root.right.next=root.next.left;

}

connect(root.left);

connect(root.right);

}

发表于 2017-08-13 12:43:53 回复(0)

Java

pp11

public class Solution {
    public void connect(TreeLinkNode root) {
        if (root == null) {
            return;        
        }
        TreeLinkNode cur = null;
        TreeLinkNode pre = null;
        TreeLinkNode nextLineFirst = null;
        cur = root;
        while (cur != null) {
            while(cur != null) {
                if (cur.left != null) {
                    if (nextLineFirst == null) {
                        nextLineFirst = cur.left;                    
                    }
                    if (pre != null) {
                        pre.next = cur.left;
                    }  
                    pre = cur.left;
                }
                if (cur.right != null) {
                    if (nextLineFirst == null) {
                        nextLineFirst = cur.right;                    
                    }                
                    if (pre != null) {
                        pre.next = cur.right;                    
                    }
                    pre = cur.right;
                }
                cur = cur.next;
            }
            pre = null;
            cur = nextLineFirst;
            nextLineFirst = null;
        }
    }
}

发表于 2017-08-01 15:21:42 回复(0)

Java

Zfirsty

//层次遍历，从右至左
public void connect(TreeLinkNode root) {
        if(root==null) return;
        LinkedList que=new LinkedList();
         que.offer(root);
        while(!que.isEmpty()){
            int size=que.size();
            TreeLinkNode pre =null;
            while (size>0){
                size--;
                TreeLinkNode p = que.poll();
                p.next=pre;
                pre=p;
                if(p.right!=null) que.offer(p.right);
                if(p.left!=null) que.offer(p.left);
            }
        }
    }

发表于 2017-07-25 15:35:31 回复(0)

Java

Holiday_12138

import java.util.*;
public class Solution {
    
    public void connect(TreeLinkNode root) {
        if(root == null)
            return;
        TreeLinkNode cur = root;
        while(cur.left != null) {
            TreeLinkNode levelCur = cur;
            while(levelCur != null) {//默认满二叉树
                levelCur.left.next = levelCur.right;
                levelCur.right.next = levelCur.next == null ? null : levelCur.next.left;
                levelCur = levelCur.next;
            }
            cur = cur.left;
        }
    }
    /*---不是常数空间
    public void connect(TreeLinkNode root) {
        if(root == null)
            return;
        Queue<TreeLinkNode> q = new LinkedList<TreeLinkNode>();
        q.add(root);
        q.add(null);
        while(!q.isEmpty()) {
            TreeLinkNode r;
            while((r = q.remove()) != null) {
                if(r.left != null)
                    q.add(r.left);
                if(r.right != null)
                    q.add(r.right);
                r.next = q.peek();
            }
            if(!q.isEmpty())
                q.add(null);
        }
    }*/
}

发表于 2017-06-26 15:17:09 回复(0)