題目描述
給定一個二叉樹，找出其最小深度，
最小深度是從根節點到最近葉子節點的最短路徑上的節點數量，
說明: 葉子節點是指沒有子節點的節點，
示例
輸入：[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/
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/93552.html
標籤：其他
上一篇：求歐拉函式（模板）
下一篇：乘法逆元（模板）