116. Populating Next Right Pointers in Each Node

You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Example 1:

Input: root = [1,2,3,4,5,6,7]
Output: [1,#,2,3,#,4,5,6,7,#]
Explanation: Given the above perfect binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.

Example 2:

Input: root = []
Output: []

思路Coding化:

class Solution:
    def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':

        cur = root
        nxt = root.left if cur else None

        while cur and nxt:
            #連接一般的:
            cur.left.next = cur.right
            #連接跨越的，如果右邊有node的話(3)(上一步驟的next產生)，連接底下跨越的node(5->6)
            if cur.next:
                cur.right.next = cur.next.left
            
            #更新cur, nxt，是否移動到next node(有無next)(2->3)
            cur = cur.next
            #如果沒有right node，則往下移動
            if not cur:
                cur = nxt
                nxt = cur.left
        return root

Time Complexity:O(N)

Space Complexity:O(1)