[LeetCode]题解（python）：117-Populating Next Right Pointers in Each Node II

题目来源：

　　https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/

题意分析：

　　根据上一题，如果给定的树不是完全树同层的连接。要求常数空间时间复杂度。如：

         1 -> NULL
       /  
      2 -> 3 -> NULL
     /     
    4-> 5 -> 7 -> NULL

题目思路：

　　用两个指针来记录下一个指针和下一层第一个指针。

代码（python）：

 1 # Definition for binary tree with next pointer.
 2 # class TreeLinkNode(object):
 3 #     def __init__(self, x):
 4 #         self.val = x
 5 #         self.left = None
 6 #         self.right = None
 7 #         self.next = None
 8 
 9 class Solution(object):
10     def connect(self, root):
11         """
12         :type root: TreeLinkNode
13         :rtype: nothing
14         """
15         if root:
16             tmp,tmp1,tmp2 = root,None,None
17             while tmp:
18                 if tmp.left:
19                     if tmp1:
20                         tmp1.next = tmp.left
21                     tmp1 = tmp.left
22                     if not tmp2:
23                         tmp2 = tmp1
24                 if tmp.right:
25                     if tmp1:
26                         tmp1.next = tmp.right
27                     tmp1 = tmp.right
28                     if not tmp2:
29                         tmp2 = tmp1
30                 tmp = tmp.next
31             self.connect(tmp2)

View Code