木構造の復習ついでに DFS に挑戦
こんばんは(*´ω`)
年末、如何お過ごしでしょうか。
私はほろ酔いで何となく DFS に挑戦したので
ホロホロっとメモしていきます。('◇')ゞ
DFS の記事は、有識者が沢山いるので
説明は省きますw
なんとなく書いて動かしてみたので
その結果を共有します。
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 show(self):
if not self.root:
print("None")
return
def DFS(node):
print(node.val)
if node.left:
DFS(node.left)
if node.right:
DFS(node.right)
return DFS(self.root)
#case 1#
### TreeImage ###
# 5 #
# / \ #
# 4 10 #
# / /\ #
# 3 6 11 #
#################
T = BinTree()
T.add(5)
T.add(4)
T.add(10)
T.add(6)
T.add(11)
T.add(3)
T.show()
#case 1#
### TreeImage ###
# 5 #
# / \ #
# 4 10 #
# / /\ #
# 3 6 11 #
#################
5
4
3
10
6
11
それとなく動いているようです。
良きかな、良きかな。。
ではでは、実践行ってみましょう。
103. Binary Tree Zigzag Level Order Traversal
Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).
For example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its zigzag level order traversal as:
[
[3],
[20,9],
[15,7]
]
ザックリ訳ですが、
二分木を渡すから、リストで返して欲しい。
但し、前述にあるようにジグザグで読みだしてね、じゃ('ω')ノ
。。的な感じです。
ココ で前述の問題は BFS で解いてますが、
DFS の勉強がてら解けないかと思い、やってみました。
一応以下の記述で通りました。
class Solution:
def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
if not root:
print("None")
return
ans = []
level = 0
def DFS(node,level):
if len(ans) == level:
ans.append([])
ans[level].append(node.val)
if node.left:DFS(node.left,level+1)
if node.right:DFS(node.right,level+1)
return ans
ZigTree = DFS(root,level)
for i in range(len(ZigTree)):
if i%2 == 1:
ZigTree[i].reverse()
return ZigTree
#28ms
うーん、再帰記述はシンプルで良いのです NE!!
次は deque でもやってみようかな(*´з`)
Author And Source
この問題について(木構造の復習ついでに DFS に挑戦), 我々は、より多くの情報をここで見つけました https://qiita.com/AKpirion/items/a97593a0b1372255bd0d著者帰属:元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Content is automatically searched and collected through network algorithms . If there is a violation . Please contact us . We will adjust (correct author information ,or delete content ) as soon as possible .