二叉树的最小深度

二叉树的最小深度

1.1、直接递归

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def minDepth(self, node: TreeNode) -> int:
        if not node:
            return 0
        if not node.left and not node.right:
            return 1
        minDepth = float('inf')
        
        if node.left:
            minDepth = min(minDepth, self.minDepth(node.left))
        if node.right:
            minDepth = min(minDepth, self.minDepth(node.right))

        return minDepth + 1

复杂度分析

• 时间复杂度：我们访问每个节点一次，时间复杂度为 O(N) ，其中 N 是节点个数。
• 空间复杂度：最坏情况下，整棵树是非平衡的，例如每个节点都只有一个孩子，递归会调用 NN （树的高度）次，因此栈的空间开销是 O(N) 。但在最好情况下，树是完全平衡的，高度只有log(N)，因此在这种情况下空间复杂度只有 O(log(N)) 。

1.2、BFS

层次遍历

class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        que = [] # 进行层次遍历
        que.append(root)
        level = 0 # 记录当前深度
        while len(que) > 0:
            queSize = len(que)
            for i in range(queSize):  # 同一层次的节点
                node = que.pop(0) # 从队列取出
                if not node.left and not node.right: # 遇到叶子节点
                    return level + 1
                if node.left:
                    que.append(node.left)
                if node.right:
                    que.append(node.right)
            level += 1
        return level
                

复杂度分析

• 时间复杂度：最坏情况下，这是一棵平衡树，我们需要按照树的层次一层一层的访问完所有节点，除去最后一层的节点。这样访问了 N/2 个节点，因此复杂度是 O(N)。
• 空间复杂度：和时间复杂度相同，也是O(N)。