找到二叉树中的最大搜索二叉子树

找到二叉树中的最大搜索二叉子树

题目：找到二叉树中的最大搜索二叉子树

《程序员代码面试指南》第37题 P121 难度：尉★★☆☆

书上原话：“本题涉及二叉树面试题中一个很常见的套路，也是全书的一个重要内容”。可见其重要性。

这个套路的名字叫做树形dp套路。

树形dp套路使用前提：如果题目求解目标是S规则，则求解流程可以定成以每一个节点为头结点的子树在S规则下的每一个答案，并且最终答案一定在其中。

以本题为例，求解流程可以定成：在整棵二叉树中，求出每一个节点为头结点的子树的最大搜索二叉子树（对任何一棵子树都求出答案），并且最终答案（整棵二叉树的最大搜索二叉子树）一定在其中。

树形dp套路第一步：以某个节点X为头结点的子树中，分析答案有哪些可能性，并且这种分析是以X的左子树、X的右子树和X整棵树的角度来考虑可能性的。

以本题举例，包含三种可能性。概括而言，最大搜索二叉子树可能来自左子树或右子树，或者是用X连起左子树和右子树所构成的整体。

树形dp套路第二步：根据第一步的可能性分析，列出所有需要的信息。

以本题举例，左树上需要的信息为leftMaxBSTHead、leftBSTSize、leftMax；右树上需要的信息为rightMaxBSTHead、rightBSTSize、rightMin。

树形dp套路第三步，合并第二步的信息，对左树和右树提出同样的要求，并写出信息结构。

以本题举例，合并成包含maxBSTHead、maxBSTSize、max和min的ReturnType类。需要通过它们来判断第一步中的三种可能性。

public class ReturnType {
    public Node maxBSTHead;
    public int maxBSTSize;
    public int min;
    public int max;

    public ReturnType(Node maxBSTHead, int maxBSTSize, int min, int max) {
        this.maxBSTHead = maxBSTHead;
        this.maxBSTSize = maxBSTSize;
        this.min = min;
        this.max = max;
    }
}

树形dp套路第四步：设计递归函数，递归函数是处理以X为头结点的情况下的答案，包括

1. 设计递归的base case（本题中即为空树的情况）
2. 直接得到左树和右树的所有信息
3. 把可能性做整合
4. 返回第三步的信息结构

代码如下：

public ReturnType process(Node X) {
    // base case : 如果子树是空树
    // 最小值为系统最大
    // 最大值为系统最小
    if (X == null) {
        return new ReturnType(null, 0, Integer.MAX_VALUE, Integer.MIN_VALUE);
    }
    // 默认直接得到左树全部信息
    ReturnType lData = process(X.left);
    // 默认直接得到右树全部信息
    ReturnType rData = process(X.right);
    // 以下过程为信息整合
    // 同时以X为头的子树也做同样的要求，也需要返回如ReturnType描述的全部信息
    // 以X为头的子树的最小值是：左树最小、右树最小、X的值，三者中最小的
    int min = Math.min(X.value, Math.min(lData.min, rData.min));
    // 以X为头的子树的最大值是：左树最大、右树最大、X的值，三者中最大的
    int max = Math.max(X.value, Math.max(lData.max, rData.max));
    // 如果只考虑可能性一和可能性二，以X为头的子树的最大搜索二叉树大小
    int maxBSTSize = Math.max(lData.maxBSTSize, rData.maxBSTSize);
    // 如果只考虑可能性一和可能性二，以X为头的子树的最大搜索二叉树头节点
    Node maxBSTHead = lData.maxBSTSize >= rData.maxBSTSize ? lData.maxBSTHead
        : rData.maxBSTHead;
    // 利用收集的信息，可以判断是否存在可能性三
    if (lData.maxBSTHead == X.left && rData.maxBSTHead == X.right
        && X.value > lData.max && X.value < rData.min) {
        maxBSTSize = lData.maxBSTSize + rData.maxBSTSize + 1;
        maxBSTHead = X;
    }
    // 信息全部搞定，返回
    return new ReturnType(maxBSTHead, maxBSTSize, min, max);
}

树形dp套路就是以上四个步骤，就是利用递归函数设计一个二叉树后序遍历的过程：先遍历左子树收集信息，然后是右子树收集信息，最后在头节点做信息整合。因为是递归函数，所以对所有的子树要求一样，都返回ReturnType的实例。依次求出每棵子树的答案，总答案一定在其中。主方法如下：

public Node getMaxBST(Node head) {
    return process(head).maxBSTHead;
}

详细解析见书P122-124。（第一次做这种树形dp套路的题，书上说后面还有一些题是用这种套路来解题，待我做到后面再多加熟练熟练）