力扣中116 填充每个节点的下一个右侧节点指针

标签：Node val int public 力扣 116 new root 节点

题解1：

 

 也就是一下就把队列里所有的元素移除了 移除的同时添加左右节点 队列中每次放的都是一层

 

题解2：

找到next可以利用next找下一节点

用pre标记每层第一个 tmp标记当前作用的 处理当前节点的左右

 

题解3 递归 左往右右往左连接 再dfs左右子树

 

 

 

 

 

 

 

 

没啥想法 想一次性一个循环就做完这个工作 但是写不出来 所以就先写了个垃圾版本

package Leetcode;

import java.util.LinkedList;
import java.util.Queue;

class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}
    
    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};

public class Leetcode116 {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Node root= new Node(1,new Node(2,new Node(4),new Node(5),null),new Node(3,new Node(6),new Node(7),null), null);
        Leetcode116.connect(root);
    }
    //深度还是不会
    public static Node connect(Node root) {
        Node temp=root;
        Queue<Node> queue=new LinkedList<Node>();
        Queue<Node> queueres=new LinkedList<Node>();
        int layer=1;//用来标记每层需要加的指针个数
        int count=0;//标记已经遍历过的节点
        if(root==null){//这个不加 对于空树会出错
            return root;
        }
        queue.add(root);
        while(!queue.isEmpty()) {
            temp=queue.poll();
            queueres.add(temp); //只要移除就压入下一个
            if(temp.left!=null) {
                queue.add(temp.left);
                queue.add(temp.right);
            }
        }
        int len=queueres.size(); //原来直接把这个放在for循环里面 导致queueres不断移除会使得for提前终止
        for(int i=0;i<len;i++) {
            temp=queueres.poll();
            count++;
 
            if((count+1)%(int)Math.pow(2,layer)==0) {
                temp.next=null;
                layer++;
            }
            else {
                temp.next=queueres.peek();
            }           
        }    
        return root;
    }

}

 

标签：Node,val,int,public,力扣,116,new,root,节点
From： https://www.cnblogs.com/ayuanjiejie/p/17195885.html