前言

在练习了一些二叉树的题目后，发现二叉树由于其自身的结构特点，很多题目都可以递归解决。

于是我想，如果你没有掌握二叉树结构或递归思想，可以通过这个章节来进行理解，提高。

我在这里搜集了一些相关的题目，分享思路并给出递归解法(部分题解法不唯一，仅供参考)。

题目主要来源：力扣

二叉树结构：

class TreeNode{
    int val;
    TreeNode left, right;
    TreeNode() {};
    TreeNode(int val){
        this.val = val;
    }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

基础

这里讲述一下二叉树和递归的基础概念，供忘了或还没有学的朋友大致了解。

二叉树

二叉树是树结构的一种情况。其中每个节点最多只有两个子节点，分别称为左子树和右子树。

在算法题中，二叉树通常具备以下特点：

结构具有明显的递归性（子树本身仍然是二叉树）
许多问题可以通过“当前节点 + 左右子树”的方式进行拆分

常见的二叉树问题包括遍历、深度/高度计算、结构变换以及基于二叉搜索树性质的判断等。

递归

递归是一种算法思想。其核心在于：将一个问题拆分为若干个规模更小但形式相同的子问题。

有一个非常经典的递归问题：汉诺塔–将n个盘子的移动问题拆解为n-1个盘子的相同问题。

概念：

在一根柱子上从下往上按照大小顺序摞着64个圆盘。把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

代码：

class HanoiTower{
    public void move(int n, char from, char to, char aux){
        if (n == 1){
            System.out.println("Move disk 1 from " + from + " to " + to);
            return;
        }
        move(n-1, from, aux, to);
        System.out.println("Move disk " + n + " from " + from + " to " + to);
        move(n-1, aux, to, from);
    }
}

方法论

分析题目是否可以递归完成 (重点看根和左右子树的关系)。
若可以递归完成，则分析根与左右子树的关系。
分别取左子树和右子树，这时左右子树又会成为两个根，而这两个根又有自己的左右子树。这样就形成了递归，由根和左右子树的关系去层层递推。
思考边界条件和返回值。

示例

题目：验证二叉树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效二叉搜索树定义如下：

节点的左子树只包含严格小于当前节点的数。
节点的右子树只包含严格大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

通过阅读题目，可以发现：我们先判断根和左右子树，当左子树比根小，右子树比根大，则这一层符合条件。
可以根据这一判断逻辑进行衍生–当左子树的左子树比左子树小，左子树右子树比左子树大，则这一层符合条件，以此类推
边界条件：当节点值超出区间时，直接返回 false。空节点视为合法，作为递归的边界条件。
返回值：返回当前节点是否有效。

class Solution {
    public boolean isValidBST(TreeNode root) {
        if (root.left == null && root.right == null) return true;
        
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    
    private boolean isValidBST(TreeNode root, long min, long max) {
        if (root == null) return true;
        if (root.val <= min || root.val >= max) return false;
        return isValidBST(root.left, min, root.val) && isValidBST(root.right, root.val, max);
    }
}

练习题目

给定一个二叉树的根节点 root ，返回它的中序遍历。

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        inorder(root, ans);
        return ans;
    }
    private void inorder(TreeNode node, List<Integer> res){
        if (node == null){
            return;
        }
        inorder(node.left, res);
        res.add(node.val);
        inorder(node.right, res);
    }
}

给定一个二叉树 root ，返回其最大深度。

二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        else if (root.left == null && root.right == null) return 1;
        else {
            int leftDepth = maxDepth(root.left);
            int rightDepth = maxDepth(root.right);
            return Math.max(leftDepth, rightDepth) + 1;
        }
    }
}

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null)   return null;
        TreeNode l = invertTree(root.left);
        TreeNode r = invertTree(root.right);
        root.left = r;
        root.right = l;
        return root;
    }
}

给你一个二叉树的根节点 root ，检查它是否轴对称。

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return check(root.left, root.right);
    }

    private boolean check(TreeNode p, TreeNode q){
        if(p == null && q == null)    return true;
        if(p == null || q == null)    return false;
        return p.val == q.val && check(p.left,q.right) && check(p.right, q.left);
    }
}

给你一棵二叉树的根节点，返回该树的直径。

二叉树的直径是指树中任意两个节点之间最长路径的长度。这条路径可能经过也可能不经过根节点 root 。

两节点之间路径的长度由它们之间边数表示。

class Solution {
    public int ans;
    public int diameterOfBinaryTree(TreeNode root) {
        dfs(root);
        return ans;
    }
    private int dfs(TreeNode node){
        if(node == null){
            return -1;
        }
        int l = dfs(node.left) + 1;
        int r = dfs(node.right) + 1;
        ans = Math.max(l + r, ans);
        return Math.max(l,r);
    }
}

DarkYellowCat's Blog

'二叉树与递归'

前言

基础

二叉树

递归

方法论

示例

练习题目