110. 平衡二叉樹
題目：
給定一個二叉樹，判斷它是否是高度平衡的二叉樹丢烘。
本題中柱宦，一棵高度平衡二叉樹定義為：一個二叉樹每個節(jié)點 的左右兩個子樹的高度差的絕對值不超過 1 。
示例：
輸入：root = [3,9,20,null,null,15,7]
輸出：true
解題思路：
平衡二叉樹需要比較的是高度播瞳，所以使用后序遍歷掸刊，遞歸三部曲：
- 明確遞歸函數(shù)的參數(shù)和返回值：參數(shù)是當(dāng)前傳入節(jié)點，返回值是以當(dāng)前傳入節(jié)點為根節(jié)點的樹的高度赢乓。
- 明確終止條件：遞歸的過程中依然是遇到空節(jié)點了為終止忧侧，返回0，表示當(dāng)前節(jié)點為根節(jié)點的樹高度為0牌芋。
- 明確單層遞歸的邏輯：分別求出其左右子樹的高度苍柏，然后如果差值小于等于1，則返回當(dāng)前二叉樹的高度姜贡，否則返回-1，表示已經(jīng)不是二叉平衡樹了棺棵。如果已經(jīng)有一邊子樹的高度是-1楼咳，那就直接向上返回-1直到最上層。
var isBalanced = function (root) {
const getHeight = (node) => {
if (!node) {
return 0;
}
const leftHeight = getHeight(node.left);
if (leftHeight === -1) {
return -1;
}
const rightHeight = getHeight(node.right);
if (rightHeight === -1) {
return -1;
}
if (Math.abs(leftHeight - rightHeight) > 1) {
return -1;
}
return 1 + Math.max(leftHeight, rightHeight);
}
const res = getHeight(root);
return res === -1 ? false : true;
};
257. 二叉樹的所有路徑
題目：
給你一個二叉樹的根節(jié)點 root 烛恤，按 任意順序 母怜，返回所有從根節(jié)點到葉子節(jié)點的路徑。
葉子節(jié)點 是指沒有子節(jié)點的節(jié)點缚柏。
示例：
輸入：root = [1,2,3,null,5]
輸出：["1->2->5","1->3"]
解題思路：
這道題目要求從根節(jié)點到葉子的路徑苹熏，所以需要前序遍歷，這樣才方便讓父節(jié)點指向孩子節(jié)點币喧，找到對應(yīng)的路徑轨域。在這個過程中，要不斷回溯到上層節(jié)點來找下一條路徑杀餐。
根據(jù)遞歸三部曲：
- 確定遞歸函數(shù)的參數(shù)和返回值：傳入根節(jié)點即可干发，路徑可以用閉包的形式來記錄。
- 確定遞歸終止條件：這道題不需要到為null的節(jié)點史翘，只要到葉子結(jié)點即可枉长。
- 確定單層遞歸邏輯：因為是前序遍歷所以要先處理中間節(jié)點冀续，中間節(jié)點要在加入完整路徑之前就加入到路徑數(shù)組中。之后判斷左右子樹需要對節(jié)點是否為空做判斷必峰，因為前置沒有過濾空節(jié)點的情況洪唐，最后還需要注意在遞歸完成后對路徑數(shù)組進行pop來回溯到上層節(jié)點。
var binaryTreePaths = function (root) {
if (!root) {
return [];
}
const res = [];
const path = [];
const traversal = (node) => {
path.push(node.val);
if (node.left === null && node.right === null) {
res.push(path.join('->'));
return;
}
if (node.left) {
traversal(node.left);
path.pop();
}
if (node.right) {
traversal(node.right);
path.pop();
}
}
traversal(root);
return res;
};
404. 左葉子之和
題目：
給定二叉樹的根節(jié)點 root 吼蚁，返回所有左葉子之和凭需。
示例：
輸入: root = [3,9,20,null,null,15,7]
輸出: 24
解釋: 在這個二叉樹中，有兩個左葉子桂敛，分別是 9 和 15功炮，所以返回 24
解題思路：
左葉子結(jié)點是左孩子不為空但是左孩子的左右孩子都為空，這種情況下的左孩子就是左葉子結(jié)點术唬。這道題因為需要一層一層的向上來傳遞加和薪伏，所以還是使用后序遍歷。
遞歸三部曲：
- 確定遞歸函數(shù)的參數(shù)和返回值：傳入樹的根節(jié)點粗仓，返回左葉子數(shù)值之和嫁怀。
- 確定終止條件：遍歷到空節(jié)點，左葉子值為0借浊。遍歷到葉子結(jié)點塘淑，左葉子值也會是0。
- 確定單層遞歸的邏輯：遍歷到左葉子節(jié)點的時候記錄數(shù)值蚂斤，右葉子節(jié)點可以直接取遞歸的值存捺。
var sumOfLeftLeaves = function (root) {
const traversal = (node) => {
if (!node) {
return 0;
}
if (node.left === null && node.right === null) {
return 0;
}
let leftNum = traversal(node.left);
if (node.left !== null && node.left.left === null && node.left.right === null) {
leftNum = node.left.val;
}
let rightNum = traversal(node.right);
const sum = leftNum + rightNum;
return sum;
}
return traversal(root);
};
