Good evening (* ´ω ｀)
How are you doing at the end of the year? Because I was tipsy and somehow challenged DFS I will make a note of it. ('◇') ゞ
DFS articles have a lot of experts I will omit the explanation w
I wrote it somehow and tried to move it Share the results.
Tree_DFS.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 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()
Execution result.py
#case 1#
### TreeImage ###
# 5 #
# / \ #
# 4 10 #
# / /\ #
# 3 6 11 #
#################
5
4
3
10
6
11
It seems to be working implicitly. Is it good, is it good? ..
Let's put it into practice. 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],
Tree_image.py
3
/ \
9 20
/ \
15 7
return its zigzag level order traversal as:
result_image.py
[
[3],
[20,9],
[15,7]
]
It's a translation, but I'll give you a binary tree, so please return it in the list. However, as mentioned above, read it in a zigzag pattern, then ('ω') no .. .. It's like that.
** here ** solves the above problem with BFS, I wondered if I could solve it after studying DFS, so I tried it. For the time being, I passed the description below.
Zig_grouping_DFS.py
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
Well, the recursive description is simple and good NE !! Let's try deque next time (* ´з`)