こんばんは(*´ω｀)
最近、leatcode の問題が少しづつ解けるようになってきました。
皆様のおかげです、有難うございます。 m(_ _)m
あくまで私見ですが、問題の傾向としてアルゴリズムの基本を
理解しているかを問われているような印象を持ちました。
まだ easy, チョット medium のレベルで恐縮ですが。。
新しい問題にチャレンジする際に行き詰ったら
基本に戻って理解を底上げすることが前進するキッカケになると思います。
行き詰った方が居たら、ぜひ基本に戻ってみることをお勧めいたします。
微力ながら次の leetcode の問題にチャレンジしたいので
基本の復習 + α(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
はい、本題です。
まずは何も見ないで
どんなツリーを作りたいか想像して書いてみました。
### 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)
イメージ通りか確認してみましょう。
確認方法ですが、deque を使います。
今日触ったばかりなのでイメージが怪しいですが、
とりあえず TreeNode を丸々バッファすることができます。
この特徴を利用して BFS で読み込むにはどうしたら良いのか検討してみました。
こんな記述はどうでしょうか。
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)
今回作成したツリーはこちらでした。
### TreeImage ###
# 0 #
# / \ #
# 1 2 #
# / \ #
# 3 4 #
# / \ #
# 5 6 #
#################
一応、イメージとしては、以下にあるように、
上から矢印の方向に、同一層の値を順番に読みだしてリストに順次格納していくつもりです(笑)
### TreeImage ###
# → 0 #
# / \ #
# → 1 2 #
# / \ #
# → 3 4 #
# / \ #
# →5 6 #
#################
そのため、配列に直して表示すると、[0,1,2,3,4,5,6] ってなるはずです。
それでは実行してみましょう。
[0, 1, 2, 3, 4, 5, 6]
うん、大丈夫そうです。
因みに、ジグザグっぽく読んでも一応 BFS ですよね？
イメージはこんな感じです。
### TreeImage ###
# → 0 #
# / \ #
# 1 2 ← #
# / \ #
# → 3 4 #
# / \ #
# 5 6 ← #
#################
ではでは行ってみましょう。
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)
### TreeImage ###
# → 0 #
# / \ #
# 1 2 ← #
# / \ #
# → 3 4 #
# / \ #
# 5 6 ← #
#################
[0, 2, 1, 3, 4, 6, 5]
OK ですね、勉強になって良かった良かった( *´艸｀)
木構造は冒頭に書いたやり方以外にもリストで作るやり方もあるようです。
やっておいた方がいいなー( ´ー｀)y-~~
多分、触ってみた感想を本誌に追記しておくと思います。
ではでは( ｀ー´)ノ
2020/12/24 update
メリークリスマス!
夫婦でクリスマスパーティーの準備と片づけをこなし、
子供を寝かしつけたつもりが、一緒に寝てしまったとしても
ちゃんと起きてプログラムを書くのであった。。。
リストで出来たツリーについてはココが分かり易かったです。
早速、パクって BFS を適用してみました。
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)
[0, 1, 2, 3, 4, 5, 6]
なるほど、昨日書いたように
基本形がイメージがあるとlist base の記述になっても
通用することが分かりました。
もう少しいじって list base の tree のイメージを
明確にしてみます、そのあとは leetcode にチャレンジです!
ではでは( ｀ー´)ノ
12/25update
ちょっと行ってみたのですが、
まだダメみたいです。
やってみたかったことは各層毎にリストでくくる作業です。
一応前述の tree の構成だと以下の記述で grouping ができました。
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)
### TreeImage ###
# 0 #
# / \ #
# 1 2 #
# / \ #
# 3 4 #
# / \ #
# 5 6 #
#################
[[0], [1, 2], [3, 4], [5, 6]]
出来たけど前述の木構造だったからできたに過ぎないかもしれません。
もう少し色々な 2 分木に対応できるように頑張ります。
2分木に関する理解が乏しいんだと思います。
大事だなー、基礎って。( ´ー｀)y-
12/25update
昨日の敗因は、各層毎の最大ノード数を Null も含めて
考えなかったからコケタ見たいです。
なので、None も含めてカウントして、
各階層をグルーピングしてみました。
ついでに 2 文探索木の書き方を復習しつつ
改善を図りました。
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()
"""
書き方はいろいろあると思いますが、
Add に関してはdef をネストし、
show に関しては def を分割してみました。
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
個人的には def のネストよりは
分割して外に出したほうが分かり易い気がします。
本質だった leetcode の問題は無事に解けました。、
色々やってみたけど、つまりはスマートな書き方じゃないので
読みにくいコードには変わりないと思います。
改善案を考えますか。。( 一一)
ともあれ基礎を振り返りつつ、自力で問題を切り抜けるのは
何とも言えませんね、達成感(*´ω｀)
ではでは('ω')ノ
12/27 update
こんばんは。
いやはや、拙い達成間に浸っていた
自分が恥ずかしい(*ﾉωﾉ)。
有識者のコードを読んで、
あまりのシンプルさに愕然としました。
今までのアプローチは各層毎に Data 有、無を
全部カウントして階層を判断していました。
でもそれって、今のバッファ出来た数だけ
queue から読み出せば、その階層を全部読み出せたことになりませんか？
そのアプローチは思いつかなかった。。。
その案を形にしたのがこちらです。
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
御見それしました m(_ _)m