专栏首页木又AI帮【leetcode刷题】T122-二叉树的最小深度

【leetcode刷题】T122-二叉树的最小深度

木又连续日更第74天(74/100)


木又的第122篇leetcode解题报告

二叉树类型第12篇解题报告

leetcode第111题:二叉树的最小深度

https://leetcode-cn.com/problems/minimum-depth-of-binary-tree


【题目】

给定一个二叉树,找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明: 叶子节点是指没有子节点的节点。

示例:
给定二叉树 [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
返回它的最小深度  2.

【思路】

对于一个节点,如果是叶子节点,则返回其深度;如果只有左孩子,则递归得到左子树的最小深度;如果只有右孩子,则递归得到右子树的最小深度;如果左右孩子节点都有,则递归得到两个子树的深度,并且取最小值。

【代码】

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
        return self.get_min_depth(root, 0)

    def get_min_depth(self, node, depth):
        # 分为四种情况:叶子节点,只有左孩子的节点,只有右孩子的节点,两个孩子都有的节点
        if not node.left and not node.right:
            return depth+1
        if node.left and node.right:
            return min(self.get_min_depth(node.left, depth+1), self.get_min_depth(node.right, depth+1))
        if node.left:
            return self.get_min_depth(node.left, depth+1)
        if node.right:
            return self.get_min_depth(node.right, depth+1)

C++版本

/**
 * 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;
        return get_min_depth(root, 0);
    }

    int get_min_depth(TreeNode* node, int depth){
        if(!node->left && !node->right)
            return depth+1;
        if(node->left && node->right)
            return min(get_min_depth(node->left, depth+1), get_min_depth(node->right, depth+1));
        if(node->left)
            return get_min_depth(node->left, depth+1);
        return get_min_depth(node->right, depth+1);
    }
};

本文分享自微信公众号 - 木又AI帮(gh_eaa31cab4b91),作者:木又

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-07-20

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【leetcode刷题】T117-二叉树的最大深度

    https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/

    木又AI帮
  • 【leetcode刷题】T121-平衡二叉树

    https://leetcode-cn.com/problems/balanced-binary-tree/

    木又AI帮
  • 【leetcode刷题】T138-找树左下角的值

    https://leetcode-cn.com/problems/find-bottom-left-tree-value/

    木又AI帮
  • Window 提权基础

    再加上个人的理解写出的关于 Windows 提权基础的文章,其中有些地方因为不太实用所以做了适当修改,感谢 @hl0rey 的帮助和建议。

    信安之路
  • NSA Shadow Brokers 漏洞预警附解决方案

    魏艾斯博客www.vpsss.net
  • CMD命令实现批量修改文件名

    批量删除文件名特定字符(含特定字符自身)前后的文字? (如:Movie_20_(528990).mpg,要求只保留528990.mpg这样的文件名)

    明哥的运维笔记
  • 《Windows Sysinternals实战指南》 全网最低价59元,我买了2本

    擅长Windows的技术人员没有不会Sysinternals的,会Sysinternals的没有不会Autoruns和Process Explorer的。我在云...

    我爱你的一诺
  • 虚拟现实强势“入侵”游戏盛典China Joy

    镁客网
  • Python中zip()函数的解释和可视化

    返回一个元组迭代器,其中第i个元组包含每个参数序列或可迭代对象中的第i个元素。当最短的可迭代输入耗尽时,迭代器将停止。使用单个可迭代参数,它将返回1元组的迭代器...

    统计学家
  • Windows 权限提升

    本篇内容是内网安全攻防:渗透测试实战指南时的阅读笔记,笔记大部分内容均来自此书,另外一部分来源于一些公开文档和非公开文档,参考链接中均有注明。

    重生信息安全

扫码关注云+社区

领取腾讯云代金券