LeetCode 117. Populating Next Right Pointers in Each Node II [Medium] [C++] 解題筆記

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.

 

Follow up:

• You may only use constant extra space.
• Recursive approach is fine, you may assume implicit stack space does not count as extra space for this problem.

 

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.

想法:

    這題類似 116. Populating Next Right Pointers in Each Node，差別在於這裡的 binary tree 不一定是 perfect binary tree ，

因此 traverse 的順序需要特別注意必須是 root->right->left 因為不是 perfect binary tree，所以對每個 root r 而言 左子點的 next 不一定

是 r 的右子點 (因為不一定有右子點)，而右子點的 next 也不一定是 root->next->left，因此我們必須要 iterative 的去找 next，當 root->next->left 和 root->next->right

都為空的時候必須繼續找 root->next->next->left or root->next->next->right 直到 next == nullptr。

所以 traverse 的時候必須是 root->right->left 才能確保在找左右子樹的next時

跟當前 root 同 level 且在當前 root 右邊的 node 的 next 皆已設定完畢。

完整程式碼:

class Solution {
public:
    Node* connect(Node* root) {
        if (root == nullptr) { return root; }
        if (root->left != nullptr) {
            if (root->right != nullptr) {
                root->left->next = root->right;
            }
            else if (root->next != nullptr) {
                Node* cur = root;
                while (cur->next && root->left->next == nullptr) {
                    root->left->next = (cur->next->left)? cur->next->left : cur->next->right;
                    cur = cur->next;
                }
            }
            else {
                root->left->next = nullptr;
            }
        }
        if (root->right != nullptr) {
            if (root->next != nullptr) {
                Node* cur = root;
                while (cur->next && !root->right->next) {
                    root->right->next = (cur->next->left)? cur->next->left : cur->next->right;                
                    cur = cur->next;
                }
            }
            else {
                root->right->next = nullptr;
            }
        }
        connect(root->right);
        connect(root->left);
        return root;
    }
};