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;
    }
}