6

LeetCode: 111. Minimum Depth of Binary Tree

 3 years ago
source link: https://mozillazg.com/2021/01/leetcode-111-minimum-depth-of-binary-tree.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

题目

原题地址：https://leetcode.com/problems/minimum-depth-of-binary-tree/

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Note: A leaf is a node with no children.

Example 1:

image

Input: root = [3,9,20,null,null,15,7]
Output: 2

Example 2:

Input: root = [2,null,3,null,4,null,5,null,6]
Output: 5

Constraints:

  • The number of nodes in the tree is in the range [0, 105].
  • -1000 <= Node.val <= 1000

解法

广度优先遍历，找到最近的那个没有子节点的节点，这个节点距离根节点的深度即为最小深度。

这个方法的 Python 代码类似下面这样:

# 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
        stack = []
        stack.append((root, 1))

        while stack:
            node, depth = stack.pop(0)
            if node.left is None and node.right is None:
                return depth

            if node.left is not None:
                stack.append((node.left, depth + 1))
            if node.right is not None:
                stack.append((node.right, depth + 1))

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK