# 求二叉树路径DFS
class TreeNode:
def __init__(self, val = None):
self.left = None
self.right = None
self.val = val
class BTree:
def insert(self,root,node): #构建二叉排序树
if root is None:
return node
if root.val < node.val:
root.right = self.insert(root.right,node)
else:
root.left = self.insert(root.left,node)
return root
def order_print(self,root):
if root is None:
return None
self.order_print(root.left)
print(root.val, end=" ")
self.order_print(root.right)
def dfs(self, root, path, path_lst):
if root:
path += str(root.val) # 每递归到一个节点就加入该path
if not root.left and not root.right: # 遇到叶子节点则把整个path加入path_lst
path_lst.append(path)
else:
path += '->'
self.dfs(root.left,path, path_lst)
self.dfs(root.right,path, path_lst)
return path_lst
def bfs(self, root):
level_order = []
que = [root]
if root == None:
return level_order
while que:
templist = []
for i in range(len(que)):
node = que.pop(0)
templist.append(node.val)
if node.left:
que.append(node.left)
if node.right:
que.append(node.right)
level_order.append(templist)
return level_order
lst = [5,1,2,3,6,8,9]
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)
bt = BTree()
# for i in range(1, len(lst)):
# bt.insert(root, TreeNode(lst[i]))
bt.order_print(root)
print()
print(bt.bfs(root))
