本文共 2045 字，大约阅读时间需要 6 分钟。

转载请注明作者和出处：

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.

题目：判断二叉树的最小深度。也就是leaf tree，从叶子到根经过的结点的最小值。

思路：判断结点是否存在左子树和右子树。如果结点存在左子树或者右子数，说明没有到叶子，需要继续查询；如果结点不存在左子树和右子数，说明已经到达叶子。例如图1二叉树示意图，该二叉树的最小深度为3，也就是1->2->4、1->3->5。需要注意的是，如果根结点(root)为空，则最小深度为0。

Language：cpp

递归方法：

/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public:    int minDepth(TreeNode* root) {        if(!root) return 0;        int l = minDepth(root->left);        int r = minDepth(root->right);        return 1 + (l && r ? min(l, r) : max(l, r));    }};

Language：python

Python使用了两种方法，递归和迭代。通过运行对比发现，迭代的方法速度更快。

递归方法：

# Definition for a binary tree node.# class TreeNode(object):#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneclass Solution(object):    def minDepth(self, root):        """        :type root: TreeNode        :rtype: int        """        if not root:            return 0        d = map(self.minDepth, (root.left, root.right))        return 1 + (min(d) or max(d))

迭代方法：

# Definition for a binary tree node.# class TreeNode(object):#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneclass Solution(object):    def minDepth(self, root):        """        :type root: TreeNode        :rtype: int        """        if not root:            return 0        queue = [root]        height = 0        while queue:            # node = queue.pop(0)            height += 1            ls = []            for temp in queue:                if not temp.right and not temp.left:                    return height                if temp.left:                    ls.append(temp.left)                if temp.right:                    ls.append(temp.right)            queue = ls        return height

代码获取：

转载地址：https://jackcui.blog.csdn.net/article/details/75043140 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！