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

# 117. Populating Next Right Pointers in Each Node II

## [題目連結:] https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/

## 題目:
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.
* The recursive approach is fine. You may assume implicit stack space does not count as extra space for this problem.


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

## 解題想法:
同類型題目: [116. Populating Next Right Pointers in Each Node](/ycdkTjYJT26U898X_34enw)

* 題目為要求把一顆完全二元樹的每層node之間順序連接
* 此題要求constant extra space
* 使用pointer
* 想法:
* 每次處理當前node的下一層進行next連結
* cur=root:
* 紀錄當前root
* 每次向右同層遍歷: cur=cur.next
* 若cur==None，則cur=head，進入下一層
* head=None:
* 用來指向下一層的最左node(第一個node)
* 每當該層走完，cur便會指向head
* pre=None:
* 用來連結next的，若當前root右邊有node，則next連結，然後pre向右移動

* 示意圖:

說明:
loop1:紅
開始cur=1,head=None,pre=None
* 因為cur.left存在，且pre=None，表示下一層還沒開始連結
* 所以head=cur.left，即head=2
* 將pre=cur.left,即pre=2
* 因為cur.right存在，且pre!=None
    所以將pre連接cur.right，即2->3
    且將pre=pre.next，pre=3
* 此cur左右子都遍歷完了,將cur=cur.next
    因為cur=None
    所以表示該層結束，cur=head移動到下層，
    同時清除head跟pre，重設為None

loop2:藍
cur=2，head=None,pre=None
* 因為cur.left存在，且pre=None
* head=4,pre=4
* 因為cur.right=5存在
    4->5，pre=pre.next，pre=5
* cur左右子遍歷完，cur=cur.next

loop3: 黑
cur=3 ,head=4,pre=5
* cur.right存在
* 5->7 ,pre=pre.next,pre=7
* cur=cur.next
    因為cur=None
    移到下層，重設head,pre

loo4~end: 紅
因為cur=4沒子樹，所以cur=cur.next，cur=5
5也沒子樹，cur=7，7也沒子樹，cur=cur.next=None

連完邊end

## Python:
* 此題真的很燒腦 :cry:
* 直接代碼上標注trace過程

#可同時解116
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
        """
        cur=root
        #head用來指向下一層的最左node
        #當每層走完 cur便會指向head
        head=None
        #pre用來連結當前遍歷到的右邊node
        #用以遍歷同時連結next
        pre=None
        while cur:                      #loop1:  cur=1                     #loop2: cur=2            
            if cur.left:                #loop1:  2存在                     #loop2: 4存在                    
                #若pre有值，則將pre.next連結到當前的node
                if pre:                                                                                  
                    pre.next=cur.left                                                                    
                    pre=pre.next
                else:                                 
                    #pre=None  表示下一行還沒開始遍歷
                    head=cur.left       #loop1:head=2                       #loop2:head=4
                    pre=cur.left        #loop1:pre=2                        #loop2:pre=2
            if cur.right:               #loop1: 3存在                       #loop2: 5存在                 
                if pre:                 #loop1:  因為pre=2 !=None                                          
                    pre.next=cur.right  #loop1:  將pre.next=3 即2->3        #loop2:  將pre.next=5 即4->5   
                    pre=pre.next        #loop1: pre=3                       #loop2: pre=5
                else:
                    head=cur.right
                    pre=cur.right
            #遍歷完左右子樹，cur移動到他的兄弟node
            cur=cur.next                #loop1: 1.next=None                 #cur=3
            #若cur==None 表示該行已遍歷完
            if cur==None:                 
                cur=head                #loop1: 遍歷下一行
                head=None               #loop1:清空head pre
                pre=None
        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()