226.翻转二叉树 （优先掌握递归）
- 两两交换节点的左右孩子（交换的是指针，不是数值）
- 这道题用前序和后序是最直接的
伪代码
//确定递归的参数(根节点)和返回值（TreeNode）
public TreeNode invertTree(TreeNode root)
//确定终止条件：碰到空节点时
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. 对称二叉树 （优先掌握递归）
思路
- 本质上是判断根节点的左右子树是否能相互翻转。
- 比较外侧和外侧，内侧和内侧节点是否相等。
- 二叉树中确定遍历顺序很重要。这道题目中只能使用后序遍历，因为要不断收集左右孩子的信息返回给上一个节点，这才能知道左右子树是否相等。需要收集孩子的信息并向上一层节点，都使用后序遍历。
伪代码
// 定义方法，确定参数和返回值。
//调用方法需要把根节点的左右孩子传入
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 != right) return false;
//左右不为空且相等，继续向下遍历
//处理单层递归中的逻辑：外侧节点相同，内侧节点相同才相同
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.二叉树的最大深度 （优先掌握递归）
题目链接/文章讲解/视频讲解
什么是深度，什么是高度，如何求深度，如何求高度，这里有关系到二叉树的遍历方式。
思路
- 深度就是二叉树中任意一个节点到根节点的距离，深度都从1开始。高度是二叉树任意一个节点到叶子节点的距离。
- 求高度：后序遍历（左右中）可以把叶子节点的高度返回给父节点，父节点+1就是高度。
- 求深度：前序遍历（中左右），往下遍历一个就+1.
- 根节点的高度就是二叉树的最大深度，所以多用后序遍历。
//确定递归的参数和返回值
public int maxDepth(TreeNode root){
//确定遍历的终止条件
if(node == null){
//此时高度为0
return 0;
}
//因为是后序遍历，所以先计算左节点高度，再计算右节点高度
int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);
//当前父节点的最大高度就是1+左右孩子的最大值
return Math.max(leftDepth, rightDepth) + 1;
// 以上3行代码可以简写成：
//return 1 + max(maxDepth(root.left), maxDepth(root.right));
}
111.二叉树的最小深度 （优先掌握递归）
题目链接/文章讲解/视频讲解
先看视频讲解，和最大深度 看似差不多，其实 差距还挺大，有坑。
思路
- 审题：根节点到最近叶子节点的距离为最小深度，null节点不算
- 求深度：还是后序遍历求高度的逻辑，求最小高度
- 为什么不用前序：代码不如后序简洁
// 定义函数返回值和参数
public int minDepth(TreeNode root){
//终止条件
if(node == null){
return 0;
}
//处理递归的单层逻辑 左右中
int leftDepth = minDepth(root.left);
int rightDepth = minDepth(root.right);
//处理中节点，要考虑左为空（取右子树的最小高度再+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;
}
}
