SpringApplication random variant smtp HammerJS 网页后台模板 前端项目实战 jquery的each循环 sallenkey滤波器 js对象添加元素 mser算法 flutter项目案例 mysql配置远程连接 mysql事务 python中index的用法 python当前日期 python正则替换 python零基础 java的substring java写入txt文件 java输出数组 java语言是什么 java怎么编程 java获取文件 java8函数式编程 网页游戏开发入门 customerrors decimalformat popen 音频录制软件 摩斯密码翻译 枪神传说辅助 小程序源码下载 html特殊字符 iphone滚动截屏 dg分区 咪咕客户端下载 kms神龙 groupy 音乐剪辑器下载
当前位置: 首页 > 学习教程  > 编程语言

C语言递归之二叉树的最小深度

2021/2/13 20:22:34 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

题目描述 给定一个二叉树,找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 说明: 叶子节点是指没有子节点的节点。 示例 输入:[3,9,20,null,null,15,7] 输出:2 题目要求 /*** Definition for a binary tree n…

题目描述

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

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

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

 

示例

输入:[3,9,20,null,null,15,7]
输出:2

 

题目要求

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

int minDepth(struct TreeNode* root){

}

 

题解

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

int dfs(int d,struct TreeNode* r){
    if(r->left==NULL&&r->right==NULL)return d+1;
    if(r->left==NULL)return dfs(d+1,r->right);
    if(r->right==NULL)return dfs(d+1,r->left);
    return fmin(dfs(d+1,r->left),dfs(d+1,r->right));
}

int minDepth(struct TreeNode* root){
    if(root==NULL)return 0;
    if(root->left==NULL&&root->right==NULL)return 1;
    if(root->left==NULL)return dfs(1,root->right);
    if(root->right==NULL)return dfs(1,root->left);
    return fmin(dfs(1,root->left),dfs(1,root->right));
}

  

搜索到叶子节点时返回深度

当前节点的左右子节点之一为空时递归非空子节点

当前节点的左右节点都不为空时递归两子节点取其最小值

 

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


本文链接: http://www.dtmao.cc/news_show_700460.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?