【典型】树的动态规划问题

1. 分析

树形动态规划问题的前提：如果题目要求的目标是规则S，则流程一般是完成每个结点为root时的子树，在规则S下的每一个答案，最终答案一定在这些答案中。

本题中，规则是整棵树的最大搜索二叉树（maxBST）。求出每一个节点作为root的子树的maxBST，最终答案一定在其中。

1.1 第一步，可能性分析

第一种可能：maxBST来自（注意，不是 “是“）X的左子树。
第二种：maxBST来自X的右子树。
第三种：X为root的树本身是maxBST。这需要两个条件。

• 条件1，X的左子树和右子树都是maxBST。
• 条件2，X.val 比左子树的val都大，比右子树的都小。

1.2 第二步，列出信息

根据可能性，列出所有需要的信息。为了分析前两个可能，需要左右子树上各自的maxBST的头部、大小。为了分析第三种可能，还需要当前结点X的值与左子树所有结点的最大值、右子树所有结点的最小值的大小。

1.3 第三步，合并信息

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

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

1.4 设计递归函数

递归函数是处理以当卡节点X为root的maxBST。需要设计递归的base case，即默认获得左右子树的ReturnType。对信息进行判断后将结果以ReturnType返回。

public ReturnType process(Node X){
        //base case
        if(X == null){
            //注意，空结点的ReturnTyoe
            //min为MAX_VALUE, 保证所有的val都比它小
            //max则反之
            return new ReturnType(null, 0, Integer.MAX_VALUE, Integer.MIN_VALUE);
        }
        //获取左右子树的ReturnTyoe
        ReturnType left = process(X.left);
        ReturnType right = process(X.right);
        //信息整合
        //如果是情况1或情况2
        Node maxBSTHead = (left.maxBSTSize >= right.maxBSTSize) ? X.left : X.right;
        int maxBSTSize = (maxBSTHead == X.left) ? left.maxBSTSize : right.maxBSTSize;
        int min = Math.min(X.val, Math.min(left.min, right.min));
        int max = Math.max(X.val, Math.max(left.max, right.min));
        //如果是情况3，有两个条件
        //条件1，X的左子树和右子树都是maxBST
        //条件2，X.val 比左子树的val都大，比右子树的都小
        //如果X是叶结点，自身就是BST
        if(left.maxBSTHead == X.left && right.maxBSTHead == X.right 
            && X.val > left.max && X.val < right.min){
                maxBSTHead = X;
                maxBSTSize = left.maxBSTSize + right.maxBSTSize + 1;
            }
        //返回ReturnTyoe
        return new ReturnType(maxBSTHead, maxBSTSi***, max);        
    }    

2. 代码

import java.util.*;
class Node {
    public int val;
    public Node left;
    public Node right;

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

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

public class Solution {
    //获取当前结点X的maxBST
    //情况1，maxBST来自（注意，不是 “是“）X的左子树
    //情况2，maxBST是X的右子树
    //情况3，maxBST是X为根的整棵树
    public ReturnType process(Node X){
        //base case
        if(X == null){
            //注意，空结点的ReturnTyoe
            //min为MAX_VALUE, 保证所有的val都比它小
            //max则反之
            return new ReturnType(null, 0, Integer.MAX_VALUE, Integer.MIN_VALUE);
        }
        //获取左右子树的ReturnTyoe
        ReturnType left = process(X.left);
        ReturnType right = process(X.right);
        //信息整合
        //如果是情况1或情况2
        Node maxBSTHead = (left.maxBSTSize >= right.maxBSTSize) ? X.left : X.right;
        int maxBSTSize = (maxBSTHead == X.left) ? left.maxBSTSize : right.maxBSTSize;
        int min = Math.min(X.val, Math.min(left.min, right.min));
        int max = Math.max(X.val, Math.max(left.max, right.min));
        //如果是情况3，有两个条件
        //条件1，X的左子树和右子树都是maxBST
        //条件2，X.val 比左子树的val都大，比右子树的都小
        //如果X是叶结点，自身就是BST
        if(left.maxBSTHead == X.left && right.maxBSTHead == X.right 
            && X.val > left.max && X.val < right.min){
                maxBSTHead = X;
                maxBSTSize = left.maxBSTSize + right.maxBSTSize + 1;
            }
        //返回ReturnTyoe
        return new ReturnType(maxBSTHead, maxBSTSi***, max);        
    }    
    public Node getMaxBST(Node head){
        return process(head).maxBSTHead;
    }
}

3. 复杂度

时间:O(n)
空间:O(h) , h为树高为栈深