題目描述
給出一個(gè)完全二叉樹(shù)，求出該樹(shù)的節(jié)點(diǎn)個(gè)數(shù)码俩。
相關(guān)話題：?樹(shù)伪阶、二分查找???難度：?中等
說(shuō)明：
完全二叉樹(shù)的定義如下：在完全二叉樹(shù)中，除了最底層節(jié)點(diǎn)可能沒(méi)填滿外粘招，其余每層節(jié)點(diǎn)數(shù)都達(dá)到最大值啥寇，并且最下面一層的節(jié)點(diǎn)都集中在該層最左邊的若干位置。若最底層為第 h 層洒扎，則該層包含1~ 2h 個(gè)節(jié)點(diǎn)辑甜。
示例：
-
遞歸
可以說(shuō)，對(duì)遞歸的執(zhí)行過(guò)程多少有點(diǎn)懵逼袍冷，在leetcode129我說(shuō)例如本題另起了一個(gè)函數(shù)sumNumbers(TreeNode root, int sum)磷醋。因?yàn)樵谒阋粭l路徑的值時(shí)，是一種自底向上的遞歸胡诗，需要接受上一步傳遞下來(lái)的結(jié)果邓线，是一步一步更新的過(guò)程，所以需要sum的輔助煌恢。
這道題我第一時(shí)間也是想著定義一個(gè)變量count隨著遞歸累加骇陈，
錯(cuò)誤做法
class Solution {
public int countNodes(TreeNode root) {
return countNodes(root,0);
}
public int countNodes(TreeNode root,int count) {
//這個(gè)返回條件就是個(gè)大大的錯(cuò)誤
if(root == null) return count;//返回一條路徑的節(jié)點(diǎn)總數(shù)
count += 1;
return countNodes(root.left,count) + countNodes(root.right,count);
}
}
這樣必定會(huì)算了很多重復(fù)的節(jié)點(diǎn)，貌似不好確定邊界症虑，除非定義一個(gè)數(shù)組類型的變量通過(guò)先序遍歷每遍歷到一個(gè)節(jié)點(diǎn)累加1缩歪。
class Solution {
public int countNodes(TreeNode root) {
return countNodes(root,new int[1]);
}
public int countNodes(TreeNode root,int[] count) {
if(root == null) return 0;
count[0] += 1;
countNodes(root.left,count);
countNodes(root.right,count);
return count[0];
}
}
-
優(yōu)雅遞歸
自頂向下，想求整棵樹(shù)的節(jié)點(diǎn)樹(shù)谍憔，就先要求左子樹(shù)和右子樹(shù)的節(jié)點(diǎn)數(shù)匪蝙，然后加上根節(jié)點(diǎn)1，就是最后的結(jié)果了习贫。這個(gè)斐波那契數(shù)列的求法一樣的逛球，是一個(gè)遞推的過(guò)程。
class Solution {
public int countNodes(TreeNode root) {
if(root == null) return 0;
return countNodes(root.left) + countNodes(root.right) + 1;
}
}
總結(jié)：遞歸使我懵逼苫昌，研究返回條件和返回后的狀態(tài)颤绕。
