111. 二叉树的最小深度

Difficulty
easy
Tags
二叉树
递归
URL
https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/
Star
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
示例 1：
notion imagenotion image
输入：root = [3,9,20,null,null,15,7]
输出：2
示例 2：
输入：root = [2,null,3,null,4,null,5,null,6]
输出：5
提示：
  • 树中节点数的范围在 [0, 105] 内
  • 1000 <= Node.val <= 1000

法1 信息传递-从上往下

思路
从上往下传递 深度信息，然后维护一个全局变量
题解
# 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:
        self.res = float("inf")
        self.helper(root=root, depth=1)
        return self.res if self.res != float("inf") else 0

    def helper(self, root, depth):
        if root is None:
            return 0

        if root.left is None and root.right is None:
            self.res = min(self.res, depth)

        self.helper(root.left, depth + 1)
        self.helper(root.right, depth + 1)

法 2 信息传递 -从下往上

思路
返回 左子树 和 右子树的最小深度，然后 min(l, r) + 1
需要专门处理 最小深度为 0 的时候，0不能作为最小深度。
题解
# 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 root is None:
            return 0
        if root.left is None and root.right is None:
            return 1

        l = self.minDepth(root.left)
        r = self.minDepth(root.right)

        # 对返回的结果进行处理
        if l == 0 or r == 0:
            return l + 1 if l > 0 else r + 1
        else:
            return min(l, r) + 1

## 改进版， 当子树为空时，返回最大值，这样取min的时候就不会取到了。但是要注意树为空的时候

class Solution:
    def minDepth(self, root: TreeNode) -> int:
        # 边界条件
        if root is None:
            return 0

        return self.helper(root)

    def helper(self, root):
        if root is None:
            return float("inf")
        if root.left is None and root.right is None:
            return 1

        l = self.helper(root.left)
        r = self.helper(root.right)

        # 对返回的结果进行处理
        return min(l, r) + 1

对法1的详细解释

思路
和
🏒
104. 二叉树的最大深度 不同的是，要排除以下情况下子树2的高度为2 而不是1 ，因为节点2 不是叶子节点。
就是说算完子树高度后，需要判断是否存在左子树为空 右子树不为空 的情况，这种情况下，该树的最小高度不是简单的取min
notion imagenotion image
题解
# Definition for a binar

y 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 root is None:
            return 0
        left_depth = self.minDepth(root.left)
        right_depth = self.minDepth(root.right)
        # 排除非叶子节点的情况
        if root.left is None:
            return 1 + right_depth
        if root.right is None:
            return 1 + left_depth
				
        depth = min(left_depth, right_depth) + 1
        return depth

------------------优雅的写法------------------
if root is None:
   return 0
if node.left is None:
		return self.MinDepth(node.right) + 1
if node.right is None:
		return self.MinDepth(node.left) + 1
return min(self.MinDepth(node.left), self.MinDepth(node.right)) + 1
本题的核心在于对最小深度的判断上，最小深度是根据叶子节点判断的。所以可以采用正常递归策略，遇到叶子节点时，将该叶子节点的深度赋值给result,且每次遇到叶子节点都去更新为最小的result.且初始有效的result或为一个超大值，或为一个有效的叶子节点的深度。
# 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:
        self.result = None
        if root is None:
            return 0
        self.dfs(node=root, depth=0)
        return self.result
    
    def dfs(self, node, depth):
        if node is None:
            return 
        if node.left is None and node.right is None:
            if self.result is None:
                self.result = depth + 1
            else:
                self.result = min(self.result, depth+1)
            return 
        self.dfs(node.left, depth+1)
        self.dfs(node.right, depth+1)

法2 层次遍历

思路
和
🏒
104. 二叉树的最大深度 区别在于不用完全遍历完所有层，只要判断到一个叶子节点即可终止循环
题解
# 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:
        result = 0
        if root is None:
            return result
        queue = []
        queue.append(root)
        while len(queue) > 0:
            temp_len = len(queue)
            while temp_len > 0:
                temp_node = queue.pop(0)
                temp_len -= 1
                # 判断是否为叶子节点 如果是，终止
                if temp_node.left is None and temp_node.right is None:
                    return result + 1
                # 不是叶子节点 保存子节点到队列
                if temp_node.left:
                    queue.append(temp_node.left)
                if temp_node.right:
                    queue.append(temp_node.right)
            result += 1
        return result
对上述代码优化，得以下代码：
# 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:
        result = 0
        if root is None:
            return result
        
        queue = []
        queue.append(root)
        while len(queue) > 0:
            # 开始新的一层
            result += 1
            len_temp = len(queue)
            while len_temp > 0:
                node = queue.pop(0)
                len_temp -= 1
                if node.left is None and node.right is None:
                    return result
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)