leetcode习题集——116. 填充每个节点的下一个右侧节点指针

题目

给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：

struct Node {

int val;

Node *left;

Node *right;

Node *next;

}

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

算法

public class P116 {
    public Node connect(Node root) {
        if(root==null){
            return root;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        int length = 1;
        while(!queue.isEmpty()){
            Node pre = null;
            for(int i=0;i<length;i++){
                Node t = queue.poll();
                if(pre!=null){
                    pre.next = t;
                }
                pre = t;
                if(i==length-1){
                    t.next = null;
                }
                if(t.left!=null){
                    queue.add(t.left);
                }
                if(t.right!=null){
                    queue.add(t.right);
                }
            }
            length=queue.size();
        }
        return root;
    }

}
           

思路：参见leetcode习题集——102. 二叉树的层次遍历

用前驱节点pre来进行next指针的赋值