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

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为树高为栈深