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指針的指派