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