# 求二叉树路径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))

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42
• 43
• 44
• 45
• 46
• 47
• 48
• 49
• 50
• 51
• 52
• 53
• 54
• 55
• 56
• 57
• 58
• 59
• 60
• 61
• 62
• 63