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

## 1.問題 

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

![](https://901207480-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGKoChvN9am4__HCIRK%2F-LNFrWJD2N9vem5CewFn%2F-LNFrqzF5m0USXowFIie%2F%E8%9E%A2%E5%B9%95%E5%BF%AB%E7%85%A7%202018-09-25%20%E4%B8%8B%E5%8D%889.15.46.png?alt=media\&token=47e0ca63-1a7e-44db-b316-18c5d522d461)

## 2.想法 <a href="#id-2-xiang-fa" id="id-2-xiang-fa"></a>

* 提問
  * 確認題意:  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.程式碼** <a href="#id-3-cheng-shi" id="id-3-cheng-shi"></a>

```
/**
 * 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;
            }
        }
    }
};
```