-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathallnodesdistancekinbinarytree.py
196 lines (173 loc) · 7.5 KB
/
allnodesdistancekinbinarytree.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
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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
#Given the root of a binary tree, the value of a target node target, and an integer k, return an array of the values of all nodes that have a distance k from the target node.
#You can return the answer in any order.
#Input: root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2
#Output: [7,4,1]
#Explanation: The nodes that are a distance 2 from the target node (with value 5) have values 7, 4, and 1.
#python3 solution:
class Solution:
def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:
self.startp = None
self.res = []
def connectparent(root, prev=None):
if not root: return
if root == target:
self.startp = root
root.parent = prev
#notice how we also pass root as prev in each iteration here, so prev changes to become the parent in each recursive call!
connectparent(root.left, root)
connectparent(root.right, root)
connectparent(root)
def findk(root, k, prev=None):
if not root:
return
if k == 0:
self.res.append(root.val)
return
#notice how we pass the current node in as prev in each turn this block executes!, so if 6's left child is not equal to prev, which starts at None, then we set prev = 6 now and continue down left!
if root.left != prev: findk(root.left, k - 1, root) #This section of the code handles the recursive traversal in three directions: left child, right child, and parent. Let's go through it step by step:
if root.right != prev: findk(root.right, k - 1, root)
if root.parent != prev: findk(root.parent, k - 1, root)
findk(self.startp, k)
return self.res
#if root.left != prev: findk(root.left, k - 1, root) line:
#If the left child of the current node (root) is not the same as the previous node (prev), it means we haven't just come from the left child. In this case, we recursively call getNodeAtKDistance with the left child as the new root, k-1 as the new distance, and the current node (root) as the new previous node. This effectively moves us one step closer to the target node along the left subtree.
#practice again:
class Solution:
def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:
self.startp = None
self.res = []
def findparent(root, prev=None):
if not root: return
if root == target: #target is a NODE here, so we don't have to use .val
self.startp = root
root.parent = prev #setting parent attribute of root to prev, which starts with none and will be modified in subsequent iterations
findparent(root.left, root)
findparent(root.right, root)
findparent(root, None)
def distancek(root, k, prev=None):
if not root: return
if k == 0:
self.res.append(root.val)
return
#prev=None first but will become root as soon as inner block executes
#we have to explore all directions
if root.left != prev: distancek(root.left, k - 1, root)
if root.right != prev: distancek(root.right, k - 1, root)
if root.parent != prev: distancek(root.parent, k - 1, root)
distancek(self.startp, k, None) #we found our target node, so we do a bfs starting from it
return self.res
#6/7/24 review:
class Solution:
def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:
self.startp = None
self.res = []
def f(root, prev=None):
if not root:
return
if root == target:
self.startp = root
root.parent = prev
f(root.left, root)
f(root.right, root)
f(root)
def a(root, k, prev=None):
if not root:
return
if k == 0:
self.res.append(root.val)
return
if root.left != prev: a(root.left, k - 1, root)
if root.right != prev: a(root.right, k - 1, root)
if root.parent != prev: a(root.parent, k - 1, root) #if you put this line above if root.left != prev, it works too! we are exploring all directions regardless of which direction you want to explore first and then backtracking
a(self.startp, k)
return self.res
#6/13/24 review:
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:
self.res = []
self.startp = None
def f(root, prev):
if not root:
return
if root == target:
self.startp = root
root.parent = prev
f(root.left, root)
f(root.right, root)
f(root, None)
def findparents(root, k, prev):
if not root:
return
if k == 0:
self.res.append(root.val)
if root.left != prev: findparents(root.left, k - 1, root)
if root.right != prev: findparents(root.right, k - 1, root)
if root.parent != prev: findparents(root.parent, k - 1, root)
findparents(self.startp, k, None)
return self.res
#6/26/24 review:
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:
self.startp = None
self.res = []
def linkparent(root, prev=None):
if not root:
return
if root == target:
self.startp = root
root.parent = prev
linkparent(root.left, root)
linkparent(root.right, root)
linkparent(root)
def traverse(root, k, prev=None):
if not root:
return
if k == 0:
self.res.append(root.val)
if root.left != prev: traverse(root.left, k - 1, root)
if root.right != prev: traverse(root.right, k - 1, root)
if root.parent != prev: traverse(root.parent, k - 1, root)
traverse(self.startp, k) #make sure to start traversing from self.startp, not root!
return self.res
#7/21/24 refresher:
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:
self.res = []
self.startp = None
def linktoparent(root, prev=None):
if not root:
return
if root == target:
self.startp = root
root.parent = prev
linktoparent(root.left, root)
linktoparent(root.right, root)
linktoparent(root)
def traverse(root, k, prev):
if not root:
return
if k == 0:
self.res.append(root.val)
if root.left != prev: traverse(root.left, k - 1, root)
if root.right != prev: traverse(root.right, k - 1, root)
if root.parent != prev: traverse(root.parent, k - 1, root)
traverse(self.startp, k, None)
return self.res