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

https://www.cnblogs.com/shi-champion/p/12262678.html

题目描述

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

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

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

示例

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

题目要求

1/**
2 * Definition for a binary tree node.
3 * struct TreeNode {
4 *     int val;
5 *     struct TreeNode *left;
6 *     struct TreeNode *right;
7 * };
8 */
9
10int minDepth(struct TreeNode* root){
11
12}

题解

1/**
2 * Definition for a binary tree node.
3 * struct TreeNode {
4 *     int val;
5 *     struct TreeNode *left;
6 *     struct TreeNode *right;
7 * };
8 */
9
10int dfs(int d,struct TreeNode* r){
11    if(r->left==NULL&&r->right==NULL)return d+1;
12    if(r->left==NULL)return dfs(d+1,r->right);
13    if(r->right==NULL)return dfs(d+1,r->left);
14    return fmin(dfs(d+1,r->left),dfs(d+1,r->right));
15}
16
17int minDepth(struct TreeNode* root){
18    if(root==NULL)return 0;
19    if(root->left==NULL&&root->right==NULL)return 1;
20    if(root->left==NULL)return dfs(1,root->right);
21    if(root->right==NULL)return dfs(1,root->left);
22    return fmin(dfs(1,root->left),dfs(1,root->right));
23}

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

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

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

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