104. 二叉樹的最大深度
題目：
給定一個二叉樹 root ，返回其最大深度殿怜。
二叉樹的 最大深度 是指從根節(jié)點(diǎn)到最遠(yuǎn)葉子節(jié)點(diǎn)的最長路徑上的節(jié)點(diǎn)數(shù)典蝌。
示例：
輸入：root = [3,9,20,null,null,15,7]
輸出：3
解題思路：
這道題可以用前序遍歷或者后序遍歷，前者求的是深度稳捆，后者求的是高度赠法。
- 二叉樹節(jié)點(diǎn)的深度：指從根節(jié)點(diǎn)到該節(jié)點(diǎn)的最長簡單路徑邊的條數(shù)或者節(jié)點(diǎn)數(shù)（取決于深度從0開始還是從1開始）
例如：深度從根節(jié)點(diǎn)開始應(yīng)該是1，2乔夯，3砖织。 - 二叉樹節(jié)點(diǎn)的高度：指從該節(jié)點(diǎn)到葉子節(jié)點(diǎn)的最長簡單路徑邊的條數(shù)或者節(jié)點(diǎn)數(shù)（取決于高度從0開始還是從1開始）
根節(jié)點(diǎn)的高度就是二叉樹的最大深度。
例如：高度從根節(jié)點(diǎn)開始應(yīng)該是3末荐，2侧纯，1。
遞歸的時候依然是三部曲：
- 確定遞歸函數(shù)的參數(shù)和返回值：參數(shù)就是傳入樹的根節(jié)點(diǎn)甲脏，返回就返回這棵樹的高度眶熬。
- 確定終止條件：如果為空節(jié)點(diǎn)的話妹笆，就返回0，表示高度為0娜氏。
- 確定單層遞歸的邏輯：先求它的左子樹的深度拳缠，再求右子樹的深度，最后取左右深度最大的數(shù)值再+1贸弥。
var maxDepth = function (root) {
const getHeight = (node) => {
if (!node) {
return 0;
}
const leftHeight = getHeight(node.left);
const rightHeight = getHeight(node.right);
return leftHeight > rightHeight ? 1 + leftHeight : 1 + rightHeight;
}
const res = getHeight(root);
return res;
};
559. N 叉樹的最大深度
題目：
給定一個 N 叉樹窟坐，找到其最大深度。
最大深度是指從根節(jié)點(diǎn)到最遠(yuǎn)葉子節(jié)點(diǎn)的最長路徑上的節(jié)點(diǎn)總數(shù)绵疲。
N 叉樹輸入按層序遍歷序列化表示哲鸳，每組子節(jié)點(diǎn)由空值分隔（請參見示例）。
輸入：root = [1,null,3,2,4,null,5,6]
輸出：3
解題思路：
整體思路和二叉樹是一致的盔憨，注意求子樹的高度的求法徙菠。
var maxDepth = function (root) {
const getHeight = (node) => {
if (!node) {
return 0;
}
let height = 0;
node.children.forEach((item) => {
height = Math.max(height, getHeight(item));
})
return height + 1;
}
return getHeight(root);
};
111. 二叉樹的最小深度
題目：
給定一個二叉樹，找出其最小深度郁岩。
最小深度是從根節(jié)點(diǎn)到最近葉子節(jié)點(diǎn)的最短路徑上的節(jié)點(diǎn)數(shù)量婿奔。
說明：葉子節(jié)點(diǎn)是指沒有子節(jié)點(diǎn)的節(jié)點(diǎn)。
示例：
輸入：root = [3,9,20,null,null,15,7]
輸出：2
解題思路：
依舊是遞歸三部曲：
- 確定遞歸函數(shù)的參數(shù)和返回值：參數(shù)為要傳入的二叉樹根節(jié)點(diǎn)驯用，返回是高度脸秽。
- 確定終止條件：終止條件也是遇到空節(jié)點(diǎn)返回0，表示當(dāng)前節(jié)點(diǎn)的高度為0蝴乔。
- 確定單層遞歸的邏輯：
- 如果左子樹為空，右子樹不為空驮樊，說明最小深度是 1 + 右子樹的深度薇正。
- 如果右子樹為空，左子樹不為空囚衔，最小深度是 1 + 左子樹的深度挖腰。 - 如果左右子樹都不為空，返回左右子樹深度最小值 + 1 练湿。
var minDepth = function (root) {
const getHeight = (node) => {
if (!node) {
return 0
}
const leftHeight = getHeight(node.left);
const rightHeight = getHeight(node.right);
if (node.left === null && node.right !== null) {
return rightHeight + 1;
}
if (node.left !== null && node.right === null) {
return leftHeight + 1;
}
return 1 + Math.min(leftHeight, rightHeight);
}
return getHeight(root);
};
222. 完全二叉樹的節(jié)點(diǎn)個數(shù)
題目：
給你一棵 完全二叉樹 的根節(jié)點(diǎn) root猴仑，求出該樹的節(jié)點(diǎn)個數(shù)。
完全二叉樹的定義如下：在完全二叉樹中肥哎，除了最底層節(jié)點(diǎn)可能沒填滿外辽俗，其余每層節(jié)點(diǎn)數(shù)都達(dá)到最大值，并且最下面一層的節(jié)點(diǎn)都集中在該層最左邊的若干位置篡诽。若最底層為第 h 層崖飘，則該層包含 個節(jié)點(diǎn)。
示例：
輸入：root = [1,2,3,4,5,6]
輸出：6
解題思路：
1. 按普通二叉樹處理
遞歸三部曲：
- 確定遞歸函數(shù)的參數(shù)和返回值：參數(shù)是樹的根節(jié)點(diǎn)杈女，返回以該節(jié)點(diǎn)為根節(jié)點(diǎn)二叉樹的節(jié)點(diǎn)數(shù)量朱浴。
- 確定終止條件：如果為空節(jié)點(diǎn)的話吊圾，就返回0，表示節(jié)點(diǎn)數(shù)為0翰蠢。
- 確定單層遞歸的邏輯：先求它的左子樹的節(jié)點(diǎn)數(shù)量项乒，再求右子樹的節(jié)點(diǎn)數(shù)量，最后取總和再加一就是目前節(jié)點(diǎn)為根節(jié)點(diǎn)的節(jié)點(diǎn)數(shù)量梁沧。
var countNodes = function (root) {
const getNum = (node) => {
if (!node) {
return 0;
}
const leftNum = getNum(node.left);
const rightNum = getNum(node.right);
return 1 + leftNum + rightNum;
}
return getNum(root);
};
2. 利用完全二叉樹的特性
完全二叉樹只要里面可以找到很多的滿二叉樹檀何，這些二叉樹的節(jié)點(diǎn)數(shù)直接計(jì)算即可。
判斷滿二叉樹的方法：遞歸左右孩子趁尼，向左遞歸的深度等于向右遞歸的深度埃碱。
接下來就是按照遞歸三部曲來處理。
var countNodes = function (root) {
const getNum = (node) => {
if (!node) {
return 0;
}
let left = node.left;
let right = node.right;
let leftDepth = 0;
let rightDepth = 0;
while (left) {
leftDepth++;
left = left.left;
}
while (right) {
rightDepth++;
right = right.right;
}
if (leftDepth === rightDepth) {
return Math.pow(2, leftDepth + 1) - 1;
}
const leftNum = getNum(node.left);
const rightNum = getNum(node.right);
return leftNum + rightNum + 1;
}
return getNum(root);
};
