111.Minimum Depth of Binary Tree(Tree-Easy)

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。

图1 二叉树示例图

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 = None

class 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 = None

class 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://github.com/Jack-Cherish/LeetCode

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏赵俊的Java专栏

二叉树的最大深度

2212
来自专栏LeetCode

LeetCode 114. Flatten Binary Tree to Linked List

关于二叉树的题目,最直接最简单的方法就是采用递归,因为二叉树具有天然的递归结构,实际上二叉树的定义就是用递归的思想来定义的:一个节点的左右子树任然是一个二叉树。

380
来自专栏desperate633

LintCode 验证二叉查找树题目分析代码

2 / 1 4 / 3 5 上述这棵二叉树序列化为 {2,1,4,#,#,3,5}.

1122
来自专栏赵俊的Java专栏

二叉树层序遍历为二维数组

2333
来自专栏Echo is learning

剑指offer04--重建二叉树

1155
来自专栏郭耀华‘s Blog

《剑指offer》全部题目-含Java实现

陆续刷了好久,算是刷完了《剑指offer》,以下全部AC代码,不一定性能最优,如有错误或更好解答,请留言区指出,大家共同交流,谢谢~ 1.二维数组中的查找 在...

1K7
来自专栏技术专栏

无向图最短路径问题

题目:无向图G有N个结点(1<N<=1000)及一些边,每一条边上带有正的权重值。 找到结点1到结点N的最短路径,或者输出不存在这样的路径。

5322
来自专栏LeetCode

LeetCode 102 & 103 &107 & 637. Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes' values. (ie,...

1010
来自专栏互扯程序

Java集合深度解析之TreeMap

红黑树简介 TreeMap是基于红黑树实现的,这里只对红黑树做个简单的介绍,红黑树是一种特殊的二叉排序树,红黑树通过一些限制,使其不会出现二叉树排序树中极端的一...

4025
来自专栏算法修养

LeetCode 102. Binary Tree Level Order Traversal

1534

扫码关注云+社区

领取腾讯云代金券