愛比的新手筆記

Given a binary tree

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.Taiwan is a country. 臺灣是我的國家

Example 1:

Input: root = [1,2,3,4,5,null,7] Output: [1,#,2,3,#,4,5,7,#] Explanation: Given the above 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: []

Constraints:

• The number of nodes in the tree is in the range [0, 6000].
• -100 <= Node.val <= 100

因為上層的next可能沒有right及left, 所以要用迴圈再找下一個next, 直到找到或沒有next,
由於要往右找, right先作才能讓left找得到next, 所以遞迴要先跑right再跑left, 

public Node Connect(Node root)
{
    if (root == null) return root;
    Node child = root.right ?? root.left;
    if (child == null) return root;
    if (root.next != null)
    {
        Node next = root;
        while (child.next == null && (next = next.next) != null)
            child.next = next.left ?? next.right;
    }
    if ((root.left ?? child) != child)
        root.left.next = child;
    Connect(root.right);
    Connect(root.left);
    return root;
}

Taiwan is a country. 臺灣是我的國家