117. 填充每個節點的下一個右側節點指針 II

題解

/*
// Definition for a Node.
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;
    }
};
*/

class Solution {
public Node connect(Node root) {
        if (root == null)
            return root;
        //cur我們可以把它看做是每一層的連結清單
        Node cur = root;
        while (cur != null) {
            //周遊目前層的時候，為了友善操作在下一
            //層前面添加一個啞結點（注意這裡是通路
            //目前層的節點，然後把下一層的節點串起來）
            Node dummy = new Node(0);
            //pre表示訪下一層節點的前一個節點
            Node pre = dummy;
            //然後開始周遊目前層的連結清單
            while (cur != null) {
                if (cur.left != null) {
                    //如果目前節點的左子節點不為空，就讓pre節點
                    //的next指向他，也就是把它串起來
                    pre.next = cur.left;
                    //然後再更新pre
                    pre = pre.next;
                }
                //同理參照左子樹
                if (cur.right != null) {
                    pre.next = cur.right;
                    pre = pre.next;
                }
                //繼續通路這樣行的下一個節點
                cur = cur.next;
            }
            //把下一層串聯成一個連結清單之後，讓他指派給cur，
            //後續繼續循環，直到cur為空為止
            cur = dummy.next;
        }
        return root;
    }
}