###### tags: `Leetcode` `medium` `tree` `python`

# 116. Populating Next Right Pointers in Each Node

## [題目連結:] https://leetcode.com/problems/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```.


#### [圖片來源:]https://leetcode.com/problems/populating-next-right-pointers-in-each-node/

## 解題想法:

* 題目為要求把一顆完全二元樹的每層node之間順序連接
* Recursive:
* root開始逐一處理下一層
* 將root.left指向root.right
* 即root.left.next=root.right
* 特別注意，若當前root，有next:
* 表示下層需連結兩個子樹:
* 當前root.left連上當前root.right
* 當前root.right須連上當前root.next.left
* 示意流程:

          1 root
    2    -->     3    root.left.next(2) = root.right(3) 
4       5   6       7  

          1 
    2 root -->     3   
4  ->  5   6       7  
root.left.next(4) = root.right(5)

          1 
    2 root -->     3   
4  ->  5  ->>>> 6       7  
if root.next:
    root.right.next(5)=root.next.left(6)

* 同類型題目: [117. Populating Next Right Pointers in Each Node II](/81N3AmEtQgKSrSKSuNqSTw)
* 為使用pointer，讓space: O(1)

## Python:

class Node(object):
    def __init__(self, val=0, left=None, right=None, next=None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
    def insertLeft(self,node):
        if self.left==None:
            self.left=Node(node)
        else:
            self.left.insertLeft(node)
    def insertRight(self,node):
        if self.right==None:
            self.right=Node(node)
        else:
            self.right.insertRight(node)
    def printTree(self):
        root=self
        stack=[root]
        res=[]
        while stack:
            root=stack.pop(0)
            res.append(root.val)
            if root.left:
                stack.append(root.left)
            if root.right:
                stack.append(root.right)
        print(res)

class Solution(object):
    def connect(self, root):
        """
        :type root: Node
        :rtype: Node
        """
        if not root:
            return None
        #判斷是否有右子即可:
        #因為完全二元樹，有右子代表一定要先有左子
        if root.right:
            root.left.next=root.right #將下層自己的左子連右子
            if root.next: #若該root還有同層next
                root.right.next=root.next.left #將下層自己的右子連自己next的左子
        self.connect(root.left)
        self.connect(root.right)
        return root      

root = Node(1)
root.insertLeft(2)
root.insertRight(3)
root.left.insertLeft(4)
root.left.insertRight(5)
root.right.insertLeft(6)
root.right.insertRight(7)
root.printTree()

result = Solution()
ans = result.connect(root)
root.printTree()