二叉树 BFS 力扣 Python

102. 二叉树的层序遍历

解题思路：
层序遍历的顺序为从上到下，从左到右依次遍历。

从上到下是通过访问根节点的左右子树遍历。

从左到右是记录每一层的节点个数，以下代码的 level 就是这个作用，这里使用了双端队列是为了推广性，如下题 103， z 形循环记录每层的结点，用列表也是可以的。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        
        if not root:
            return []
        
        #加入根节点
        queue = [root]
        res = []

        while queue:
            #每层节点
            level = deque()

            size = len(queue)

            for _ in range(size):
                cur = queue.pop(0)
                level.append(cur.val)

                if cur.left:
                    queue.append(cur.left)
                
                if cur.right:
                    queue.append(cur.right)
                
            if level:
                res.append(list(level))
        return res
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

103. 二叉树的锯齿形层序遍历

解题思路：
定义一个 flag作为记录，奇数正向，偶数逆向。

双端队列可以很方便的前后增加元素。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        
        #加入根节点
        queue = [root]
        res = []
        flag = True

        while queue:
            #每层节点
            level = deque() #deque

            size = len(queue)

            for _ in range(size):
                cur = queue.pop(0)
                if flag:
                    level.append(cur.val)
                else:
                    level.appendleft(cur.val)

                if cur.left:
                    queue.append(cur.left)

                if cur.right:
                    queue.append(cur.right)

            if level:
                res.append(list(level))
            flag = not flag
        return res
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

107. 二叉树的层序遍历 II

解题思路：
如题 102，这道题只颠倒每层记录的节点顺序就可以。

注意一点，相信很多人想用 reverse() 直接颠倒列表顺序，但这个函数调用后是不会返回列表的，所以还是用切片的方式来颠倒每层节点的顺序。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
            
        if not root:
            return []
        
        #加入根节点
        queue = [root]
        res = []

        while queue:
            #每层节点
            level = deque()

            size = len(queue)

            for _ in range(size):
                cur = queue.pop(0)
                level.append(cur.val)

                if cur.left:
                    queue.append(cur.left)
                
                if cur.right:
                    queue.append(cur.right)
                
            if level:
                res.append(list(level))
        return res[::-1]
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

111. 二叉树的最小深度

解题思路：
BFS 记录每层的高度即可，然后选择最小深度即可。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def minDepth(self, root: TreeNode) -> int:
            
        if not root:
            return 0
        
        #加入根节点
        queue = [root]
        
        depth = 1
        while queue:

            size = len(queue)

            for _ in range(size):
                cur = queue.pop(0)
                if not cur.left and not cur.right:
                    return depth

                if cur.left:
                    queue.append(cur.left)
                
                if cur.right:
                    queue.append(cur.right)
                
            depth += 1
        return depth
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

DFS 也可以解决这道题，如下注释。

class Solution:
    def minDepth(self, root: TreeNode) -> int:
    	if not root:
            return 0

        left = self.minDepth(root.left)
        right = self.minDepth(root.right)
        
        if not root.left and not root.right: #没有子节点为叶子节点
            return 1

        min_depth =  0xffffff 
		
		#分别对比左右子树，选择最短路径上的节点个数
        if root.left:
            min_depth = min(left,min_depth)
        if root.right:
            min_depth = min(right, min_depth) 
            
        return min_depth + 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

另外一种 DFS写法，本质是一样的，
额外列举一个函数的好处是，
内部函数的 base case 可以直接用于记录空节点的返回数值，用于从
不需要额外的变量储存用于比较的 min_depth。

class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if not root: #判断根节点
            return 0
        def dfs(node):
            if not node: # base case 记录一个数值用于比较
                return float("inf")
            elif not node.left and not node.right:
                return 1
            return min(dfs(node.left) , dfs(node.right)) + 1
        return dfs(root)
1
2
3
4
5
6
7
8
9
10
11

BFS 算法和 DFS算法的一大区别就是，BFS 第一次搜索到的结果是最优的，但是空间复杂度高。

DFS 时间复杂较高，因为 DFS 要探索所有的节点后才能知道哪个结果是最优的。