117. Populating Next Right Pointers in Each Node IIㄟˋ大

1.問題

• 將next指向右邊的node, 且tree不是perfect

2.想法

• 提問

  • 確認題意: binary tree的類型, 若非perfect tree, 則無法確定left或right一定存在

• function header, parameter

• test input

• 說明想法

  • 用一個虛擬節點pHead及指標pre

    • 讓pHead->next指向該層的第一個node

    • 如果root->left存在, 則讓pre->next移動到root->left

    • 如果root->right存在, 則讓pre->next移動到root->right

  • 當root->next存在, 則移動root到root->next

  • 當root->next不存在時, 表示該層的node已經搜尋完, 則讓root移動到 pHead->next

• 測試計算複雜度

3.程式碼

/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  TreeLinkNode *left, *right, *next;
 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 * };
 */
class Solution {
public:
    void connect(TreeLinkNode *root) {
        TreeLinkNode* pHead = new TreeLinkNode(0), *pre = pHead;
        while (root) {
            //連結同一層的節點
            if (root->left) {
                pre->next = root->left;
                pre = pre->next;
            }
            if (root->right) {
                pre->next = root->right;
                pre = pre->next;
            }
            root = root->next;
            
            //如果同一層搜完了
            if (!root) {
                root = pHead->next;
                pre = pHead;
                pHead->next = NULL;
            }
        }
    }
};