/
Populating Next Right Pointers in Each Node II.py
77 lines (69 loc) · 2.02 KB
/
Populating Next Right Pointers in Each Node II.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
# Definition for binary tree with next pointer.
# class TreeLinkNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
# self.next = None
class Solution:
# @param root, a tree node
# @return nothing
def connect(self, root):
dummychild = TreeLinkNode(0)
while root:
cur = dummychild
dummychild.next = None
while root:
if root.left:
cur.next = root.left
cur = cur.next
if root.right:
cur.next = root.right
cur = cur.next
root = root.next
root = dummychild.next
class Solution:
def first(self, root):
while root:
if root.left:
return root.left
elif root.right:
return root.right
root = root.next
return None
def helper(self, root):
if not root:
return
while root:
if root.left:
root.left.next = root.right if root.right else self.first(root.next)
if root.right:
root.right.next = self.first(root.next)
root = root.next
# @param root, a tree node
# @return nothing
def connect(self, root):
while root:
self.helper(root)
root = self.first(root)
# not O(1)
class Solution:
# @param root, a tree node
# @return nothing
def connect(self, root):
if root == None:
return
lists = []
lists.append(root)
while lists:
next = []
for i, item in enumerate(lists):
if i != 0:
lists[i - 1].next = lists[i]
if i == len(lists) - 1:
lists[i].next = None
if item.left:
next.append(item.left)
if item.right:
next.append(item.right)
lists = next