旅游網(wǎng)站首頁(yè)圖片最近的新聞大事10條
給定一個(gè)二叉樹(shù),找出其最小深度。
最小深度是從根節(jié)點(diǎn)到最近葉子節(jié)點(diǎn)的最短路徑上的節(jié)點(diǎn)數(shù)量。
說(shuō)明:葉子節(jié)點(diǎn)是指沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)。
思路一:遞歸
int minDepth(struct TreeNode* root){if(!root)return 0;int left=minDepth(root->left),right=minDepth(root->right);return (left && right) ? 1+fmin(left,right):1+left+right;
}
分析:
本題與求二叉樹(shù)最大深度的題很像,先判斷根節(jié)點(diǎn),再遞歸看左右子樹(shù)最小值返回最小深度,由于根節(jié)點(diǎn)若在的話至少有一個(gè)節(jié)點(diǎn)所有最小深度+1
總結(jié):
本題考察二叉樹(shù)計(jì)算深度,利用遞歸可以解決