leetcode/116-populating-next-right-pointers-in-each-node.py at master · anantkaushik/leetcode · GitHub

Name: leetcode/116-populating-next-right-pointers-in-each-node.py at master · anantkaushik/leetcode · GitHub
Rating: 4.6 (1583 reviews)
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
"""
Problem Link: https://leetcode.com/problems/populating-next-right-pointers-in-each-node/

Given a binary tree

struct TreeLinkNode {
 TreeLinkNode *left;
 TreeLinkNode *right;
 TreeLinkNode *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.

Note:
You may only use constant extra space.
Recursive approach is fine, implicit stack space does not count as extra space for this problem.
You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).
Example:

Given the following perfect binary tree,

 1
 / \
 2 3
 / \ / \
4 5 6 7
After calling your function, the tree should look like:

 1 -> NULL
 / \
 2 -> 3 -> NULL
 / \ / \
4->5->6->7 -> NULL
"""
"""
# Definition for a Node.
class Node:
 def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
 self.val = val
 self.left = left
 self.right = right
 self.next = next
"""
classSolution:
defconnect(self, root: 'Node') ->'Node':
ifnotroot:
return

self.dfs(root)
returnroot


defdfs(self, root, next_node=None):
ifnotroot:
return

root.next=next_node
self.dfs(root.left, root.right)
self.dfs(root.right, root.next.leftifroot.nextelseNone)


classSolution1:
defconnect(self, root: 'Node') ->'Node':
ifnotroot:
return

self.dfs(root)
returnroot


defdfs(self, root, parent=None):
ifnotroot:
return

cur=None
whileparent:
parent.left.next=parent.right
ifnotcur:
cur=parent.right
else:
cur.next=parent.left
cur=parent.right
parent=parent.next

self.dfs(root.left, root)

classSolution2:
defconnect(self, root: 'Node') ->'Node':
ifnotroot:
return

self.dfs(root)
returnroot


defdfs(self, root, next_node=None):
ifnotroot:
return

root.next=next_node

n1=root.right
n2=root.next.leftifroot.nextelseNone
n3=root.next.rightifroot.nextelseNone
next_node=n1orn2orn3
ifroot.left:
self.dfs(root.left, next_node)
ifroot.right:
ifnext_node==n1:
next_node=n2orn3
elifnext_node==n2:
next_node=n3
else:
next_node=None
self.dfs(root.right, next_node)


classSolution3:
# @param root, a tree link node
# @return nothing
defconnect(self, root):
current= [root] ifrootelse []
whilecurrent:
nex= []
prev=None
fornincurrent:
ifprev:
prev.next=n
prev=n
ifn.left:
nex.append(n.left)
ifn.right:
nex.append(n.right)
current=nex