226.翻轉二叉樹 （優(yōu)先掌握遞歸）
- 兩兩交換節(jié)點的左右孩子（交換的是指針，不是數(shù)值）
- 這道題用前序和后序是最直接的
偽代碼
//確定遞歸的參數(shù)(根節(jié)點)和返回值（TreeNode）
public TreeNode invertTree(TreeNode root)
//確定終止條件：碰到空節(jié)點時
if(root == null) return null;
//遍歷順序：中，左，右
//中間的邏輯 swap(root.left, root.right)
invertTree(root.left);
inverTree(root.right);
swapChildren(root);
return root
swapChildren(TreeNode root){
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
}
為什么中序遍歷不行：如果是3層的二叉樹，把swap放在左右中間，此時的右子樹就不是原來的右子樹了
101. 對稱二叉樹 （優(yōu)先掌握遞歸）
思路
- 本質(zhì)上是判斷根節(jié)點的左右子樹是否能相互翻轉。
- 比較外側和外側，內(nèi)側和內(nèi)側節(jié)點是否相等。
- 二叉樹中確定遍歷順序很重要。這道題目中只能使用后序遍歷，因為要不斷收集左右孩子的信息返回給上一個節(jié)點，這才能知道左右子樹是否相等。需要收集孩子的信息并向上一層節(jié)點，都使用后序遍歷。
偽代碼
// 定義方法，確定參數(shù)和返回值。
//調(diào)用方法需要把根節(jié)點的左右孩子傳入
private boolean compare(TreeNode left, TreeNode right) {
//確定終止條件
//左節(jié)點為空，右節(jié)點不為空
if(left == null && right != null) return false;
//左不為空，右為空
else if(left != null && right == null) return false;
//左右都為空
else if(left == null && right == null) return true;
//左右都不為空，但值不相等
else if(left != right) return false;
//左右不為空且相等，繼續(xù)向下遍歷
//處理單層遞歸中的邏輯：外側節(jié)點相同，內(nèi)側節(jié)點相同才相同
boolean outSide = compare(left.left, right.right)
boolean inSide = compare(right.left, left.right)
boolean result = outSide &&inSide;
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 isSymmetric(TreeNode root) {
return compare(root.left, root.right);
}
private boolean compare(TreeNode left, TreeNode right){
if(left != null && right == null) return false;
else if(left == null && right != null) return false;
else if(left == null && right == null) return true; //這一行要寫在值比較之前
else if(left.val != right.val) return false; // 這一行注意是left.val，比較值，不要直接寫left==right
boolean outSide = compare(left.left, right.right);
boolean inSide = compare(left.right, right.left);
return outSide && inSide;
}
}
104.二叉樹的最大深度 （優(yōu)先掌握遞歸）
題目鏈接/文章講解/視頻講解
什么是深度，什么是高度，如何求深度，如何求高度，這里有關系到二叉樹的遍歷方式。
思路
- 深度就是二叉樹中任意一個節(jié)點到根節(jié)點的距離，深度都從1開始。高度是二叉樹任意一個節(jié)點到葉子節(jié)點的距離。
- 求高度：后序遍歷（左右中）可以把葉子節(jié)點的高度返回給父節(jié)點，父節(jié)點+1就是高度。
- 求深度：前序遍歷（中左右），往下遍歷一個就+1.
- 根節(jié)點的高度就是二叉樹的最大深度，所以多用后序遍歷。
//確定遞歸的參數(shù)和返回值
public int maxDepth(TreeNode root){
//確定遍歷的終止條件
if(node == null){
//此時高度為0
return 0;
}
//因為是后序遍歷，所以先計算左節(jié)點高度，再計算右節(jié)點高度
int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);
//當前父節(jié)點的最大高度就是1+左右孩子的最大值
return Math.max(leftDepth, rightDepth) + 1;
// 以上3行代碼可以簡寫成：
//return 1 + max(maxDepth(root.left), maxDepth(root.right));
}
111.二叉樹的最小深度 （優(yōu)先掌握遞歸）
題目鏈接/文章講解/視頻講解
先看視頻講解，和最大深度 看似差不多，其實 差距還挺大，有坑。
思路
- 審題：根節(jié)點到最近葉子節(jié)點的距離為最小深度，null節(jié)點不算
- 求深度：還是后序遍歷求高度的邏輯，求最小高度
- 為什么不用前序：代碼不如后序簡潔
// 定義函數(shù)返回值和參數(shù)
public int minDepth(TreeNode root){
//終止條件
if(node == null){
return 0;
}
//處理遞歸的單層邏輯 左右中
int leftDepth = minDepth(root.left);
int rightDepth = minDepth(root.right);
//處理中節(jié)點，要考慮左為空（取右子樹的最小高度再+1）；右為空（取左子樹的最小高度再+1）的情況，而不是取左右子樹最小值。
if(root.left == null) return rightDepth + 1;
if(root.right == null) return leftDepth +1;
//處理左右子樹不為null的情況
return Math.min(leftDepth, rightDepth) + 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 int minDepth(TreeNode root) {
if(root == null) return 0;
int leftDepth = minDepth(root.left);
int rightDepth = minDepth(root.right);
if(root.left == null) return rightDepth + 1;
if(root.right == null) return leftDepth + 1;
return Math.min(leftDepth,rightDepth) + 1;
}
}
