二叉树递归套路：从树形信息到问题建模

1. 引言

在算法领域，二叉树是数据结构中的常客，也是面试和竞赛中的高频考点。许多二叉树问题，如判断平衡性、搜索性、求解最大距离等，看似千变万化，实则背后隐藏着一套统一的解题范式。

本文将深入探讨这套“递归套路”，它也被称为树形动态规划（Tree DP）的一种体现。其核心思想不再是简单地遍历节点，而是定义一套“信息”规约，让每个节点都能从其子节点获取所需信息，进而“加工”出服务于其父节点的“信息”。通过理解这套范式，我们将能够系统性地攻克大部分二叉树问题。

2. 核心思想：递归套路

在处理任何一个二叉树问题时，我们都可以尝试遵循以下六个步骤来构建我们的递归函数：

假设： 假设以任意节点 X 为头，我们可以向 X 的左子树和右子树索要任何我们想要的信息。
讨论： 在上一步的假设下，分析以 X 为头节点的树，其最终答案有哪几种可能性。这是最重要的一步，它决定了我们需要哪些信息。
确定： 根据所有可能性，反推出我们到底需要向左树和右树索要哪些具体的信息。
汇总： 将左树和右树需要的信息求一个“全集”，这个全集将构成一个信息体（例如一个 Info 类），作为我们递归函数的统一返回类型。
递归： 递归函数必须返回这个 Info 信息体，每一棵子树都遵循这个“承诺”。
实现： 编写递归函数。在函数体中，我们拿到左树的 Info 和右树的 Info，然后根据第 2 步的讨论，组合加工出当前 X 节点的 Info 并返回。

3. 经典应用实例

3.1 判断是否为平衡二叉树

问题： 检查一个二叉树是否是平衡二叉树（任意节点的左右子树高度差不超过 1）。

思路分析（套用六步法）：
1. (假设) 假设我们能拿到左、右子树的任何信息。
2. (讨论) 以 X 为头的树，它“不平衡”的可能性有三种：
  - X 的左树已经不平衡了。
  - X 的右树已经不平衡了。
  - X 的左、右树都平衡，但它们的高度差超过了 1。
3. (确定) 根据第 2 步，我们发现，为了做出判断，必须向子树索要两个信息：
  - 子树是否平衡 (boolean isBalanced)
  - 子树的高度 (int height)
4. (汇总) 我们定义 Info 类，包含 height 和 isBalanced。
5. (递归) 递归函数 process(Node x) 返回 Info。
6. (实现)
  - base case: 如果 x == null，返回 new Info(0, true)（空树高度为 0，且是平衡的）。
  - 拿到 leftInfo 和 rightInfo。
  - height = Math.max(leftInfo.height, rightInfo.height) + 1。
  - isBalanced = leftInfo.isBalanced 且 rightInfo.isBalanced 且 Math.abs(leftInfo.height - rightInfo.height) <= 1。
  - 返回新的 Info。
代码实现：

java

public class isBalancedTree {

    // 判断是否是平衡二叉树（并非AVL）
    // 这里的平衡二叉树：子树高度差不超过1
    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }

    /**
     * 头结点能从子树获得的子树信息：
     * 1. 该子树高度
     * 2. 子树是否平衡
     */
    public static class Info {
        public int height;
        public boolean isBalanced;

        public Info(int height, boolean isBalanced) {
            this.height = height;
            this.isBalanced = isBalanced;
        }
    }

    /**
     * 实现方法：
     * 1. 获取左右子树的信息
     * 2. 满足条件：左树是，右树是，左右两树高度差不超过1
     */
    public static boolean isBT(Node root) {
        return process(root).isBalanced;
    }

    public static Info process(Node x) {
        if (x == null) {
            return new Info(0, true);
        }

        Info leftInfo = process(x.left);
        Info rightInfo = process(x.right);

        int height = 1;
        height += Math.max(leftInfo.height, rightInfo.height);

        boolean isBalanced = true;
        if (!leftInfo.isBalanced) isBalanced = false;
        if (!rightInfo.isBalanced) isBalanced = false;
        if (Math.abs(leftInfo.height - rightInfo.height) > 1) isBalanced = false;

        return new Info(height, isBalanced);
    }

}

3.2 判断是否为满二叉树

问题： 检查一个二叉树是否是满二叉树（所有非叶子节点都有两个子节点，且所有叶子节点都在同一层）。

思路分析：
1. 以 X 为头的树，它是“满”的充要条件是：
  - X 的左树是满的。
  - X 的右树是满的。
  - X 的左树高度 == X 的右树高度。
2. 我们需要向子树索要两个信息：
  - 子树是否为满 (boolean isFull)
  - 子树的高度 (int height)
3. - base case: x == null，返回 new Info(0, true)（空树是满的）。
  - 拿到 leftInfo 和 rightInfo。
  - height = Math.max(leftInfo.height, rightInfo.height) + 1。
  - isFull = leftInfo.isFull 且 rightInfo.isFull 且 leftInfo.height == rightInfo.height。
代码实现：

java

public class IsFullBT {

    // 是否是满二叉树：
    // 每个非叶子节点都有两个子节点。
    // 所有叶子节点都位于同一层。
    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }

    /**
     * 头结点能从子树获得的信息：
     * 1. 该子树的高度
     * 2. 该子树是否是满二叉树
     */
    public static class Info {
        public int height;
        public boolean isFull;

        public Info(int height, boolean isFull) {
            this.height = height;
            this.isFull = isFull;
        }
    }

    /**
     * 实现方法：
     * 1. 获取左子树、右子树的信息
     * 2. 判断是否是满二叉树：左树是，右树是，且高度相等
     */
    public static boolean isFullBT(Node root) {
        if (root == null) return true;
        return process(root).isFull;
    }

    public static Info process(Node x) {
        if (x == null) {
            return new Info(0, true);
        }

        Info leftInfo = process(x.left);
        Info rightInfo = process(x.right);

        int height = 1;
        height += Math.max(leftInfo.height, rightInfo.height);

        boolean isFull = true;
        if (!leftInfo.isFull) isFull = false;
        if (!rightInfo.isFull) isFull = false;
        if (leftInfo.height != rightInfo.height) isFull = false;

        return new Info(height, isFull);
    }
}

3.3 判断是否为搜索二叉树 (BST)

问题： 检查一个二叉树是否是搜索二叉树（BST）（中序遍历有序，或任意节点的值 > 左子树所有节点的值，且 < 右子树所有节点的值）。

思路分析：
1. 以 X 为头的树，它是 BST 的充要条件：
  - X 的左树是 BST。
  - X 的右树是 BST。
  - X.value > X 左树的最大值。
  - X.value < X 右树的最小值。
2. 我们需要向子树索要三个信息：
  - 子树是否为 BST (boolean isBST)
  - 子树的最大值 (int max)
  - 子树的最小值 (int min)
3. - base case: x == null。这里需要特别注意。您的代码中 base case 返回 null，这会导致后续逻辑中需要大量的 if (leftInfo != null) 判断。
  - isBST = leftInfo.isBST 且 rightInfo.isBST 且 ( leftInfo == null 或 leftInfo.max < x.value ) 且 ( rightInfo == null 或 rightInfo.min > x.value )。
  - max = Math.max(x.value, leftInfo != null ? leftInfo.max : x.value, rightInfo != null ? rightInfo.max : x.value) (逻辑合并后)。
  - min = Math.min(x.value, leftInfo != null ? leftInfo.min : x.value, rightInfo != null ? rightInfo.min : x.value)。
代码实现：

java

public class IsBalancedSearchTree {

    // 判断一棵二叉树是否是搜索二叉树
    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }

    /**
     * 头结点X能从子树获得的该子树信息：
     * 1. 是否是搜索二叉树
     * 2. 最大值
     * 3. 最小值
     */
    public static class Info {
        public boolean isBST;
        public int max;
        public int min;

        public Info(boolean isBST, int max, int min) {
            this.isBST = isBST;
            this.max = max;
            this.min = min;
        }
    }

    /**
     * 方法：判断二叉树是否是搜索二叉树
     * 1. 从左子树获取信息，从右子树获取信息
     * 2. 依据情况判断是否是搜索二叉树，只有左子树是，右子树是，
     * 且头结点值大于左子树max，小于右子树min才是
     */
    public static boolean isBST(Node root) {
        if (root == null) {
            return true;
        }
        return process(root).isBST;
    }

    private static Info process(Node x) {
        if (x == null) {
            return null;
        }

        Info leftInfo = process(x.left);
        Info rightInfo = process(x.right);

        int max = x.value;
        if (leftInfo != null) {
            max = Math.max(leftInfo.max, max);
        }
        if (rightInfo != null) {
            max = Math.max(rightInfo.max, max);
        }

        int min = x.value;
        if (leftInfo != null) {
            min = Math.min(leftInfo.min, min);
        }
        if (rightInfo != null) {
            min = Math.min(rightInfo.min, min);
        }

        boolean isBST = true;
        if (leftInfo != null && !leftInfo.isBST) {
            isBST = false;
        }
        if (rightInfo != null && !rightInfo.isBST) {
            isBST = false;
        }
        if (leftInfo != null && leftInfo.max >= x.value) {
            isBST = false;
        }
        if (rightInfo != null && rightInfo.min <= x.value) {
            isBST = false;
        }

        return new Info(isBST, max, min);
    }

}

3.4 求解二叉树的最大距离

问题： 求解二叉树中任意两个节点之间的最大距离（距离定义为路径上的节点数）。

思路分析：
1. 以 X 为头的树，其最大距离有三种可能性：
  - p1：最大距离完全在 X 的左子树中（与 X 无关）。
  - p2：最大距离完全在 X 的右子树中（与 X 无关）。
  - p3：最大距离穿过 X，即从 X 左子树的某个最深节点，经过 X，到达 X 右子树的某个最深节点。这个距离 = 左树高度 + 1 + 右树高度。
2. 我们需要向子树索要两个信息：
- 子树内部的最大距离 (int range)
- 子树的高度 (int height) (用于计算 p3)
1. - base case: x == null，返回 new Info(0, 0)。
  - 拿到 leftInfo 和 rightInfo。
  - height = Math.max(leftInfo.height, rightInfo.height) + 1。
  - range = Math.max(leftInfo.range, rightInfo.range, leftInfo.height + rightInfo.height + 1) (取三种可能性的最大值)。
代码实现：

java

public class BTMaxDistance {

    // 给定一棵二叉树的头节点head，任何两个节点之间都存在距离，返回整棵二叉树的最大距离
    // 注意这里的距离指的是：从一个结点出发到目标结点所经过的结点数（包括出发和目标节点）
    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }

    /**
     * 头结点能从子树获得的信息：
     * 1. 该子树的最大距离
     * 2. 该子树的高度
     */
    public static class Info {
        public int range;
        public int height;

        public Info(int range, int height) {
            this.range = range;
            this.height = height;
        }
    }

    /**
     * 实现方法：
     * 1. 从左子树、右子树分别获取信息
     * 2. 判断几种可能性：
     * 2.1 最大距离出自左子树中
     * 2.2 最大距离出自右子树中
     * 2.3 最大距离跨越头结点（可能直达另一子树的最深结点）
     */
    public static int maxDistance(Node root) {
        if (root == null) return 0;
        return process(root).range;
    }

    public static Info process(Node x) {
        if (x == null) {
            return new Info(0, 0);
        }

        Info leftInfo = process(x.left);
        Info rightInfo = process(x.right);

        int height = Math.max(leftInfo.height, rightInfo.height) + 1;

        int p1 = leftInfo.range;
        int p2 = rightInfo.range;
        int p3 = leftInfo.height + 1 + rightInfo.height;
        int range = Math.max(p1, Math.max(p2, p3));

        return new Info(range, height);
    }

}

3.5 求解最大二叉搜索子树 (Max Sub-BST) 大小

问题： 找到二叉树中，符合 BST 条件的子树中，节点数最多的那个子树的大小。

思路分析： 这是递归套路的一个复杂但极佳的例子。
1. 以 X 为头的树，其“最大 BST 子树”有三种可能性：
- p1：最大 BST 子树在 X 的左子树中（与 X 无关）。
- p2：最大 BST 子树在 X 的右子树中（与 X 无关）。
- p3：以 X 为头的整棵树恰好就是一棵 BST。
1. - 为了知道 p1 和 p2，我们必须向子树索要：int maxSubBSTSize。
  - 为了判断 p3，我们必须满足：
    - X 的左子树是 BST。
    - X 的右子树是 BST。
    - X.value > X 左树的最大值。
    - X.value < X 右树的最小值。
  - 这里有一个巧妙的设计（如您的注释所述）：我们如何知道左/右子树是不是 BST？我们可以要求子树返回它的 int size。如果 leftInfo.maxSubBSTSize == leftInfo.size，则说明左子树本身就是一棵 BST。
  - 因此，为了判断 p3，我们需要：maxSubBSTSize, size, max, min。
  - 如果 p3 成立，那么 X 树的 BST 大小就是 leftInfo.size + rightInfo.size + 1。
2. 我们需要向子树索要四个信息：
- int maxSubBSTSize (子树中最大 BST 的大小)
- int size (子树的总大小)
- int max (子树的最大值)
- int min (子树的最小值)
1. - base case: x == null。同样，您的代码返回 null，需要大量 null 检查。
  - 获取 leftInfo, rightInfo。
  - 计算 size, max, min (这三个值的计算与 3.3 节中 BST 的计算类似)。
  - 计算 p1 = leftInfo != null ? leftInfo.maxSubBSTSize : 0。
  - 计算 p2 = rightInfo != null ? rightInfo.maxSubBSTSize : 0。
  - 判断 p3 是否成立：
    - leftIsBST = leftInfo == null || (leftInfo.maxSubBSTSize == leftInfo.size)
    - rightIsBST = rightInfo == null || (rightInfo.maxSubBSTSize == rightInfo.size)
    - xBiggerThanLeft = leftInfo == null || (x.val > leftInfo.max)
    - xSmallerThanRight = rightInfo == null || (x.val < rightInfo.min)
  - 如果 p3 成立（四个条件均满足），则 p3 = (leftInfo == null ? 0 : leftInfo.size) + (rightInfo == null ? 0 : rightInfo.size) + 1。
  - maxSubBSTSize = Math.max(p1, Math.max(p2, p3))。
  - 返回新的 Info。
代码实现：

java

public class MaxSubBSTSize {

    // 找到最大二叉搜索子树的大小
    public static class Node {
        public int val;
        public Node left;
        public Node right;

        public Node(int value) {
            val = value;
        }
    }

    /**
     * 头结点能从子树获得的信息：
     * 1. 该子树有多少个结点
     * 2. 该子树中最大二叉搜索树结点数
     * 3. 该子树的最大值
     * 4. 该子树的最小值
     */
    public static class Info {
        public int size;
        public int maxSubBSTSize;
        public int max;
        public int min;

        public Info(int size, int maxSubBSTSize, int max, int min) {
            this.size = size;
            this.maxSubBSTSize = maxSubBSTSize;
            this.max = max;
            this.min = min;
        }
    }

    /**
     * 实现方法：
     * 1. 从左子树、右子树分别获得信息
     * 2. 如果左右都是二叉搜索树，并且头结点的值大于左边最大值，小于右边最小值
     * 那么当前头结点的子树是二叉搜索，并记录结点数：左子 + 右子 + 1（头）
     * 3. 注意：当最大二叉搜索树结点数 = 当前结点数时，那这棵树就是二叉搜索树
     * 这样可以省去一个变量isBST
     */
    public static int maxSubBSTSize(Node root) {
        if (root == null) return 0;
        return process(root).maxSubBSTSize;
    }

    public static Info process(Node x) {
        if (x == null) {
            return null;
        }

        Info leftInfo = process(x.left);
        Info rightInfo = process(x.right);

        int size = 1;
        if (leftInfo != null) {
            size += leftInfo.size;
        }
        if (rightInfo != null) {
            size += rightInfo.size;
        }

        int max = x.val;
        if (leftInfo != null) {
            max = Math.max(leftInfo.max, max);
        }
        if (rightInfo != null) {
            max = Math.max(rightInfo.max, max);
        }

        int min = x.val;
        if (leftInfo != null) {
            min = Math.min(leftInfo.min, min);
        }
        if (rightInfo != null) {
            min = Math.min(rightInfo.min, min);
        }


        int p1 = leftInfo != null ? leftInfo.maxSubBSTSize : -1;    // 是左子树的
        int p2 = rightInfo != null ? rightInfo.maxSubBSTSize : -1;  // 是右子树的

        // 是整体的
        int p3 = -1;
        boolean leftIsBST = leftInfo == null || (leftInfo.maxSubBSTSize == leftInfo.size);
        boolean rightIsBST = rightInfo == null || (rightInfo.maxSubBSTSize == rightInfo.size);
        boolean xBiggerThanLeft = leftInfo == null || (x.val > leftInfo.max);
        boolean xSmallerThanRight = rightInfo == null || (x.val < rightInfo.min);

        if (leftIsBST && rightIsBST && xBiggerThanLeft && xSmallerThanRight) {
            int leftSize = leftInfo == null ? 0 : leftInfo.size;
            int rightSize = rightInfo == null ? 0 : rightInfo.size;
            p3 = leftSize + rightSize + 1;
        }
        int maxSubBSTSize = Math.max(p1, Math.max(p2, p3));

        return new Info(size, maxSubBSTSize, max, min);
    }

}

4. 特殊情况：非递归套路解法

4.1 判断是否为完全二叉树 (CBT)

虽然也可以使用递归套路来解（需要的信息会更复杂，例如：子树是否为满、是否为 CBT、高度），但实现起来远不如**层序遍历（BFS）**来得直观和简洁。

思路分析（层序遍历）：
1. 使用一个队列进行层序遍历。
2. 设置一个布尔标记 leaf = false。
3. 遍历节点时：
  - 情况 1： 如果一个节点 poll 只有右孩子（poll.left == null）而没有左孩子（poll.right != null），则它一定不是完全二叉树，返回 false。
  - 情况 2： 如果我们已经遇到过一个不双全的节点（即 leaf == true），那么当前节点 poll 必须是叶子节点（poll.left == null && poll.right == null）。如果此时 poll 又有任何孩子（如代码中的 poll.right == null 判断应为 poll.left != null || poll.right != null，不过原代码的逻辑 if (leaf && poll.right == null) 似乎有误，应为 if (leaf && (poll.left != null || poll.right != null))），则返回 false。
  - 触发标记： 当我们遍历到一个节点 poll，它如果只有左孩子（poll.left != null && poll.right == null）或者它是一个叶子节点（poll.left == null && poll.right == null），我们将 leaf 标记设为 true。这表示从今往后，我们遇到的所有节点都必须是叶子。
代码实现：

java

import java.util.LinkedList;
import java.util.Queue;

public class IsCompleteBT {

    // 判断一个二叉树是否是完全二叉树

    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }

    /**
     * 层序遍历结点
     * 两种情况违背：
     * 1. 对于一个结点，如果该结点只有右孩子而没有左孩子，那么不满足完全二叉树
     * 2. 在已经发现一个不双全的结点且没有违背1的情况下，又发现一个非叶子结点，那么不满足CBT
     */
    public boolean isCBT1(Node root) {
        if (root == null) return true;

        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        boolean leaf = false;

        while(!queue.isEmpty()) {
            // 是否已经遇到不双全结点，开启情况2验证
            Node poll = queue.poll();

            if (leaf && poll.right == null) {
                return false;
            }
            if (poll.left == null && poll.right != null) {
                return false;
            }
            if (poll.left != null) {
                queue.add(poll.left);
            }
            if (poll.right != null) {
                queue.add(poll.right);
            }
            if (poll.left != null && poll.right == null) {
                leaf = true;
            }
        }
        return true;
    }


}