您好,登錄后才能下訂單哦!
如何解析python二叉樹的最小深度,相信很多沒(méi)有經(jīng)驗(yàn)的人對(duì)此束手無(wú)策,為此本文總結(jié)了問(wèn)題出現(xiàn)的原因和解決方法,通過(guò)這篇文章希望你能解決這個(gè)問(wèn)題。
給定一個(gè)二叉樹,找出其最小深度。
最小深度是從根節(jié)點(diǎn)到最近葉子節(jié)點(diǎn)的最短路徑上的節(jié)點(diǎn)數(shù)量。
說(shuō)明: 葉子節(jié)點(diǎn)是指沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)。
示例:
給定二叉樹 [3,9,20,null,null,15,7]
,
3
/ \
9 20
/ \
15 7
返回它的最小深度 2
.
標(biāo)簽:DFS
終止條件、返回值和遞歸過(guò)程:
當(dāng)前節(jié)點(diǎn)root為空時(shí),說(shuō)明此處樹的高度為0,0也是最小值
當(dāng)前節(jié)點(diǎn)root的左子樹和右子樹都為空時(shí),說(shuō)明此處樹的高度為1,1也是最小值
如果為其他情況,則說(shuō)明當(dāng)前節(jié)點(diǎn)有值,且需要分別計(jì)算其左右子樹的最小深度,返回最小深度+1,+1表示當(dāng)前節(jié)點(diǎn)存在有1個(gè)深度
時(shí)間復(fù)雜度:O(n),n為樹的節(jié)點(diǎn)數(shù)量
Java版本
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int minDepth(TreeNode root) {
if(root == null) {
return 0;
}
if(root.left == null && root.right == null) {
return 1;
}
int ans = Integer.MAX_VALUE;
if(root.left != null) {
ans = Math.min(minDepth(root.left), ans);
}
if(root.right != null) {
ans = Math.min(minDepth(root.right), ans);
}
return ans + 1;
}
}
JavaScript版本
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var minDepth = function(root) {
if(root == null) {
return 0;
}
if(root.left == null && root.right == null) {
return 1;
}
let ans = Number.MAX_SAFE_INTEGER;
if(root.left != null) {
ans = Math.min(minDepth(root.left), ans);
}
if(root.right != null) {
ans = Math.min(minDepth(root.right), ans);
}
return ans + 1;
};
看完上述內(nèi)容,你們掌握如何解析python二叉樹的最小深度的方法了嗎?如果還想學(xué)到更多技能或想了解更多相關(guān)內(nèi)容,歡迎關(guān)注億速云行業(yè)資訊頻道,感謝各位的閱讀!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。