110.平衡二叉樹 （優(yōu)先掌握遞歸）
題目鏈接/文章講解/視頻講解
再一次涉及到差油，什么是高度，什么是深度鹊碍，可以鞏固一下厌殉。
思路
- 任何節(jié)點的左右子樹高度差小于等于1則是平衡二叉樹
- 高度和深度：高度：到葉子節(jié)點的距離；深度：到根節(jié)點的距離侈咕。這道題求高度公罕，就是后序遍歷。
偽代碼
//定義遞歸函數(shù)耀销，參數(shù)和返回值
private int getHeight(TreeNode root){
//終止條件 空節(jié)點高度為0
if(node == null) return 0;
//發(fā)現(xiàn)任何一個節(jié)點不符合平衡二叉樹的定義楼眷，直接返回-1
//采用后序遍歷 左右中
int leftHeight = getHeight(root.left); //左子樹高度
if(leftHeight == -1) return -1; //左子樹高度==-1不符合平衡二叉樹
int rightHeight = getHeight(root.right); //右子樹高度
if(rightHeight == -1) return -1;
int result;
// 一定要把中寫在左右子樹的后面，才能獲取左右的情況返回給父節(jié)點
if(Math.abs(leftHeight - rightHeight) > 1){ //相減絕對值大于1
result = -1;
}else{
// 左右子樹高度取最大值再加一
result = Math.max(leftHeight, rightHeight) + 1;
}
return result;
}
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean isBalanced(TreeNode root) {
return getHeight(root) != -1; //為什么這里要這么寫
}
private int getHeight(TreeNode root){
if(root == null) return 0;
int leftHeight = getHeight(root.left);
if(leftHeight == -1) return -1;
int rightHeight = getHeight(root.right);
if(rightHeight == -1) return -1;
return Math.abs(leftHeight - rightHeight) > 1 ? -1 : (Math.max(leftHeight, rightHeight) + 1);
}
}
257. 二叉樹的所有路徑 （優(yōu)先掌握遞歸）
思路
- 返回從根節(jié)點到葉子節(jié)點的所有路徑
- 使用前序遍歷：這樣才能讓父節(jié)點指向孩子節(jié)點熊尉，才能把路徑輸出出來
- 只要有遞歸就一定有回溯
- 為什么會有回收的過程：一個容器來收集路徑罐柳，怎么把一條路徑收集完后，把子節(jié)點彈出去狰住，重新回到根節(jié)點記錄新路徑呢张吉？所以有回溯。
偽代碼
//1. 定義函數(shù)催植，定義參數(shù)和返回值
// root 根節(jié)點肮蛹； paths 記錄單條路徑的數(shù)組勺择；res 記錄最后結果，也是返回值
private void traversal(TreeNode node, List<Integer> paths, List<String> res) {
//3. 前序遍歷伦忠，中節(jié)點省核，因為遍歷到葉子節(jié)點就結束了，所以要把葉子節(jié)點放進入才中止
paths.add(node.val);
//2. 確定終止條件：遍歷到葉子節(jié)點
if(node.left == null && node.right == null){
// 要把paths轉化成String然后元素之間加上"->"昆码，代碼略
StringBuilder sb = new StringBuilder();// StringBuilder用來拼接字符串
……
res.add(sb.toString())
return;
}
//向左遞歸
if(node != null){
traversal(root.left, paths, res);
paths.remove(paths.size() - 1);// 回溯气忠，可以隱藏在參數(shù)中
}
//向右遞歸
if（node != null）{
traversal(root.right, paths, res);
paths.remove(paths.size() - 1);// 回溯
}
}
}
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<String> binaryTreePaths(TreeNode root) {
List<String> res = new ArrayList<>();// 存最終的結果
if (root == null) {
return res;
}
List<Integer> paths = new ArrayList<>();// 作為結果中的路徑
traversal(root, paths, res);
return res;
}
private void traversal(TreeNode root, List<Integer> paths, List<String> res){
paths.add(root.val);
if(root.left == null && root.right == null){
StringBuilder s = new StringBuilder();
for(int i = 0; i < paths.size()-1; i++){
s.append(paths.get(i)).append("->");
}
s.append(paths.get(paths.size() - 1));
res.add(s.toString());
return;
}
if(root.left != null){
traversal(root.left, paths, res);
paths.remove(paths.size()-1);
}
if(root.right != null){
traversal(root.right, paths, res);
paths.remove(paths.size()-1);
}
}
}
404.左葉子之和 （優(yōu)先掌握遞歸）
題目鏈接/文章講解/視頻講解
其實本題有點文字游戲，搞清楚什么是左葉子赋咽，剩下的就是二叉樹的基本操作旧噪。
思路
- 左葉子節(jié)點的定義：一定是葉子節(jié)點（子節(jié)點為空）；一定是父節(jié)點的左孩子冬耿。
- 和之前二叉樹題目的區(qū)別：無法判斷葉子節(jié)點是不是父節(jié)點的左孩子舌菜，所以判斷條件是：一個節(jié)點的左孩子不為空，同時左孩子的左右孩子都為空亦镶。
- 使用后序遍歷日月，因為要一層一層向上返回
偽代碼
public int sumOfLeftLeaves(TreeNode root) {
//終止條件
if(root == null) return 0;
if(root.left == null && root.right == null) return 0; // 不寫也行，只是遞歸多了一層
//單層遞歸的邏輯
int leftNum = sumOfLeftLeaves(root.left);
//左孩子不為空缤骨，同時左孩子為葉子節(jié)點
if(root.left != null && root.left.left != null && root.right.right != null){
leftNum = root.left.val;
}
int rightNum = sumOfLeftLeaves(root.right);
int sum = leftNum + rightNum
return sum;
}
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int sumOfLeftLeaves(TreeNode root) {
if (root == null) return 0;
if (root.left == null && root.right == null) return 0;
int leftValue = sumOfLeftLeaves(root.left); // 左
if (root.left != null && root.left.left == null && root.left.right == null) { // 左子樹就是一個左葉子的情況
leftValue = root.left.val;
}
int rightValue = sumOfLeftLeaves(root.right); // 右
int sum = leftValue + rightValue; // 中
return sum;
}
}
222.完全二叉樹的節(jié)點個數(shù)（優(yōu)先掌握遞歸）
題目鏈接/文章講解/視頻講解
需要了解爱咬，普通二叉樹 怎么求，完全二叉樹又怎么求
思路
- 如果是普通的二叉樹绊起，就是遍歷節(jié)點
后序遍歷
class Solution {
// 通用遞歸解法
public int countNodes(TreeNode root) {
if(root == null) {
return 0;
}
return countNodes(root.left) + countNodes(root.right) + 1;
}
}
- 利用完全二叉樹的特性的寫法
- 完全二叉樹的定義：除了底層節(jié)點每一層都是滿的精拟，底層節(jié)點都集中在該層最左邊
- 只要知道深度，節(jié)點數(shù)量就是2的深度次方 -1
- 所以就是左子樹的數(shù)量+右子樹的數(shù)量+1
- 如果是滿二叉樹虱歪，往左右兩邊遍歷的深度相等蜂绎；如果子樹不相等則不是滿二叉樹，那么就繼續(xù)向下遞歸笋鄙，一定可以遇到符合滿足條件的節(jié)點
public int countNodes(TreeNode root) {
//終止條件
if (root == null) return 0;
//遇到子樹為滿二叉樹师枣，也要返回結果并終止
TreeNode left = root.left;
TreeNode right = root.right;
int leftDepth = 0, rightDepth = 0; // 這里初始為0是有目的的，為了下面求指數(shù)方便
while (left != null) { // 求左子樹深度
left = left.left;
leftDepth++;
}
while (right != null) { // 求右子樹深度
right = right.right;
rightDepth++;
}
if (leftDepth == rightDepth) {
return (2 << leftDepth) - 1; // 注意(2<<1) 相當于2^2萧落，所以leftDepth初始為0
}
return countNodes(root.left) + countNodes(root.right) + 1;
}
}
