Good evening (* ´ω ｀)
Recently, I've been able to solve the leatcode problem little by little. Thanks to everyone, thank you. m (_ _) m
In my opinion, the basics of the algorithm as a tendency of the problem I had the impression that I was asked if I understood it. I'm sorry at the level of easy, chot medium. ..
If you get stuck when trying a new problem I think that returning to the basics and raising the level of understanding will be the key to moving forward. If anyone gets stuck, I recommend you to go back to the basics.
I want to challenge the next leetcode problem with a little effort I decided to write this magazine as a basic review + α (study of deque).
time stamp 2020 12/23 :release 2020 12/24 :Add list tree 2020 12/25 :Add grouping sample_r0 2020 12/26 :Add grouping sample_r1, Add sample def nest ver 2020 12/27 :Add other approach
Yes, this is the main subject. Don't look at anything first I imagined what kind of tree I wanted to make and wrote it.
myTree.py
### TreeImage ###
# 0 #
# / \ #
# 1 2 #
# / \ #
# 3 4 #
# / \ #
# 5 6 #
#################
class tree_node:
def __init__(self,val,left=None,right=None):
self.val = val
self.left = left
self.right = right
class tree:
def __init__(self):
self.root = None
def add_left(self,val):
if not self.root:
self.root = tree_node(val)
else:
if not self.root.left:
self.root.left = tree_node(val)
else:
runner = self.root
while runner.left:
runner = runner.left
runner.left = tree_node(val)
def add_right(self,val):
if not self.root:
self.root = tree_node(val)
else:
if not self.root.right:
self.root.right = tree_node(val)
else:
runner = self.root
while runner.right:
runner = runner.right
runner.right = tree_node(val)
T = tree()
T.add_left(0)
T.add_left(1)
T.add_left(3)
T.add_left(5)
T.add_right(2)
T.add_right(4)
T.add_right(6)
Let's check if it matches the image. As a confirmation method, use deque. The image is suspicious because I just touched it today, For the time being, you can buffer the entire TreeNode. I tried to find out how to use this feature to read with BFS. How about such a description?
myTree.py
def show(self):
head = self.root
q = deque([head])
ans = []
while q:
nums = q.popleft()
if not nums:
continue
ans.append(nums.val)
if nums.left or nums.right:
q.append(nums.left)
q.append(nums.right)
print(ans)
The tree created this time was here.
tree_image.py
### TreeImage ###
# 0 #
# / \ #
# 1 2 #
# / \ #
# 3 4 #
# / \ #
# 5 6 #
#################
For the time being, as an image, as shown below, From the top, in the direction of the arrow, I will read the values of the same layer in order and store them in the list (laugh)
tree_image.py
### TreeImage ###
# → 0 #
# / \ #
# → 1 2 #
# / \ #
# → 3 4 #
# / \ #
# →5 6 #
#################
Therefore, if you convert it to an array and display it, it should be [0,1,2,3,4,5,6]. Let's run it.
Execution result.py
[0, 1, 2, 3, 4, 5, 6]
Yeah, it looks okay. By the way, even if you read it like a zigzag, it's BFS, right? The image looks like this.
tree_image.py
### TreeImage ###
# → 0 #
# / \ #
# 1 2 ← #
# / \ #
# → 3 4 #
# / \ #
# 5 6 ← #
#################
Let's go.
myTree.py
def show(self):
head = self.root
q = deque([head])
ans = []
i = 0
while q:
if i%2 == 0:
nums = q.popleft()
else:
nums = q.pop()
if not nums:
continue
ans.append(nums.val)
if nums.left or nums.right:
q.append(nums.left)
q.append(nums.right)
i += 1
print(ans)
Execution result.py
### TreeImage ###
# → 0 #
# / \ #
# 1 2 ← #
# / \ #
# → 3 4 #
# / \ #
# 5 6 ← #
#################
[0, 2, 1, 3, 4, 6, 5]
It's OK, I'm glad I learned (* ´ 艸 ｀) There seems to be a way to make a tree structure with a list other than the method described at the beginning. You should do it (´ ー ｀) y- ~~ Perhaps I will add the impressions I have touched to this magazine. Then (`) no
2020/12/24 update Merry Christmas! The couple prepares and cleans up the Christmas party, I intended to put my child to sleep, but even if I fell asleep with him I got up and wrote the program. .. ..
** Coco ** was easy to understand for the tree made from the list. Immediately, I tried to apply BFS.
listedTree.py
from collections import deque
def binary_tree(r = None):
return [r,[],[]]
def put_root(root,new_val):
root[0] = new_val
def insert_left(root,new_branch):
t = root.pop(1)
if t:
root.insert(1,[new_branch,t,[]])
else:
root.insert(1,[new_branch,[],[]])
return root
def insert_right(root,new_branch):
t = root.pop(2)
if t:
root.insert(2,[new_branch,[],t])
else:
root.insert(2,[new_branch,[],[]])
return root
def show(root):
q = deque([root])
ans = []
while q:
nums = q.popleft()
if not nums:
continue
ans.append(nums[0])
if nums[1] or nums[2]:
q.append(nums[1])
q.append(nums[2])
print(ans)
r = binary_tree()
### TreeImage ###
# 0 #
# / \ #
# 1 2 #
# / \ #
# 3 4 #
# / \ #
# 5 6 #
#################
put_root(r,0)
insert_left(r,5)
insert_right(r,6)
insert_left(r,3)
insert_right(r,4)
insert_left(r,1)
insert_right(r,2)
show(r)
Execution result.py
[0, 1, 2, 3, 4, 5, 6]
I see, as I wrote yesterday If the basic form has an image, even if it becomes a description of list base It turned out to work.
Tweak a little more to get an image of the list base tree Let's clarify, then challenge leetcode! Then (`) no
12/25update I went a little, but It looks like it's still useless.
What I wanted to do was to list each layer. For the time being, with the above-mentioned tree configuration, grouping was possible with the following description.
grouping_test.py
def Add_layer(self):
return []
def show(self):
head = self.root
q = deque([head])
ANS = []
ANS.append(self.Add_layer())
i = 0
cnt = 1
while q:
nums = q.popleft()
if not nums:
cnt += 1
continue
if cnt <= 2**i:
ANS[i].append(nums.val)
print(f"{ANS[i]}")
if cnt == 2**i:
cnt = 0
i += 1
ANS.append(self.Add_layer())
cnt += 1
if nums.left or nums.right:
q.append(nums.left)
q.append(nums.right)
print(ANS)
Execution result.py
### TreeImage ###
# 0 #
# / \ #
# 1 2 #
# / \ #
# 3 4 #
# / \ #
# 5 6 #
#################
[[0], [1, 2], [3, 4], [5, 6]]
It was possible, but it may only be possible because it had the above-mentioned wooden structure. I will do my best to handle various binary trees.
I think I have a poor understanding of binary trees. It's important, the basics. (´ ー ｀) y-
12/25update The cause of yesterday's defeat was the maximum number of nodes for each layer, including Null. I didn't think about it, so I want to see it. So, count including None, I tried grouping each layer.
By the way, while reviewing how to write a two-sentence search tree I tried to improve it.
Grouping_BinTree.py
from collections import deque
class Node:
def __init__(self,val,right=None,left=None):
self.val = val
self.left = left
self.right = right
class BinaryTree:
def __init__(self):
self.root = None
def add(self,val):
if not self.root:
self.root = Node(val)
#print(self.root.val)
else:
self.add_node(self.root,val)
def add_node(self,node,val):
if val < node.val:
if not node.left:
node.left = Node(val)
#print(f"left val is {node.left.val}")
else:
self.add_node(node.left,val)
if val > node.val:
if not node.right:
node.right = Node(val)
#print(f"right val is {node.right.val}")
else:
self.add_node(node.right,val)
def add_layer(self):
return []
def show(self):
p = self.root
q = deque()
q.append(p)
ans = []
ans.append(self.add_layer())
#print(p.val,p.left.val,p.left.left.val)
i = 0
Ncnt = 0
Dcnt = 0
while q:
nums = q.popleft()
if not nums:
Ncnt += 1
print(f"Layer:{i+1},Dcnt:{Dcnt},Ncnt:{Ncnt}")
if Dcnt + Ncnt <= 2**i:
if Dcnt + Ncnt == 2**i:
Dcnt,Ncnt =0,2*Ncnt
i += 1
ans.append(self.add_layer())
continue
else:
Dcnt += 1
print(f"Layer:{i+1},Dcnt:{Dcnt},Ncnt:{Ncnt}")
ans[i].append(nums.val)
print(ans)
if Dcnt + Ncnt <= 2**i:
if Dcnt + Ncnt == 2**i:
Dcnt,Ncnt =0,2*Ncnt
i += 1
ans.append(self.add_layer())
q.append(nums.left)
q.append(nums.right)
while not ans[-1]:
ans.pop(-1)
print(ans)
#case 1#
### TreeImage ###
# 5 #
# / \ #
# 4 10 #
# / /\ #
# 3 6 11 #
#################
T = BinaryTree()
T.add(5)
T.add(4)
T.add(10)
T.add(6)
T.add(11)
T.add(3)
T.show()
"""
#case 2#
### TreeImage ###
# 5 #
# / #
# 4 #
# / #
# 3 #
#################
T = BinaryTree()
T.add(5)
T.add(4)
T.add(3)
T.show()
"""
I think there are many ways to write it, For Add, nest def and For show, I tried splitting def.
BinTree_grouping.py
from collections import deque
class Node:
def __init__(self,val,left = None,right = None,):
self.val = val
self.left = left
self.right = right
class BinTree:
def __init__(self):
self.root = None
def add(self,val):
def add_node(node,val):
runner = node
if val < runner.val:
if not runner.left:
runner.left = Node(val)
else:
add_node(runner.left,val)
if val > runner.val:
if not runner.right:
runner.right = Node(val)
else:
add_node(runner.right,val)
if not self.root:
self.root = Node(val)
else:
add_node(self.root,val)
def add_layer(self):
return []
def Manage_Control(self):
if self.Dcnt + self.Ncnt <= 2**self.i:
if self.Dcnt + self.Ncnt == 2**self.i:
self.Dcnt,self.Ncnt =0,2*self.Ncnt
self.i += 1
self.ans.append(self.add_layer())
def show(self):
p = self.root
q = deque()
q.append(p)
self.ans = []
self.ans.append(self.add_layer())
#print(p.val,p.left.val,p.left.left.val)
self.i = 0
self.Ncnt = 0
self.Dcnt = 0
while q:
nums = q.popleft()
if not nums:
self.Ncnt += 1
print(f"Layer:{self.i+1},Dcnt:{self.Dcnt},Ncnt:{self.Ncnt}")
self.Manage_Control()
continue
else:
self.Dcnt += 1
print(f"Layer:{self.i+1},Dcnt:{self.Dcnt},Ncnt:{self.Ncnt}")
self.ans[self.i].append(nums.val)
print(self.ans)
self.Manage_Control()
q.append(nums.left)
q.append(nums.right)
while not self.ans[-1]:
self.ans.pop(-1)
print(self.ans)
#case 2#
### TreeImage ###
# 5 #
# / #
# 4 #
# / #
# 3 #
#################
T = BinaryTree()
T.add(5)
T.add(4)
T.add(3)
T.show()
#120ms
Personally, rather than nesting defs I think it's easier to understand if you divide it and put it outside.
The essential leetcode problem was solved successfully. , I tried various things, but in other words, it's not a smart way of writing I don't think it will change to hard-to-read code. Do you think of an improvement plan? .. (11)
Anyway, looking back on the basics and getting through the problem on your own I can't say anything, a sense of accomplishment (* ´ω ｀)
Then ('ω') no
12/27 update Good evening. No, I was immersed in my poor achievement I'm embarrassed (* noωno).
Read the code of an expert, I was surprised at how simple it was. The approach so far is with or without data for each layer. I counted everything and judged the hierarchy.
But that's just the number of buffers I have now Isn't it possible to read the entire hierarchy by reading from the queue? I couldn't think of that approach. .. .. Here is the idea.
BFS_grouping.py
def show(self):
q = deque([self.root])
ans = []
level = 0
while q:
ans.append([])
layer_length = len(q)
for _ in range(layer_length):
nums = q.popleft()
ans[level].append(nums.val)
if nums.left:
q.append(nums.left)
if nums.right:
q.append(nums.right)
level += 1
print(ans)
#28ms
I saw it m (_ _) m
Recommended Posts