[数据结构与算法]LeetCode 1373 Maximum Sum BST in Binary Tree (DFS DP 推荐)

Given a?binary tree?root, the task is to return the maximum sum of all keys of?any?sub-tree which is also a Binary Search Tree (BST).

Assume a BST is defined as follows:

• The left subtree of a node contains only nodes with keys?less than?the node's key.
• The right subtree of a node contains only nodes with keys?greater than?the node's key.
• Both the left and right subtrees must also be binary search trees.

Example 1:

?

Input: root = [1,4,3,2,4,2,5,null,null,null,null,null,null,4,6]
Output: 20
Explanation: Maximum sum in a valid Binary search tree is obtained in root node with key equal to 3.

Example 2:

?

Input: root = [4,3,null,1,2]
Output: 2
Explanation: Maximum sum in a valid Binary search tree is obtained in a single root node with key equal to 2.

Example 3:

Input: root = [-4,-2,-5]
Output: 0
Explanation: All values are negatives. Return an empty BST.

Example 4:

Input: root = [2,1,3]
Output: 6

Example 5:

Input: root = [5,4,8,3,null,6,3]
Output: 7

Constraints:

• The?given binary tree will have between?1?and?40000?nodes.
• Each node's value is between?[-4 * 10^4?, 4 * 10^4].

题目链接：https://leetcode.com/problems/maximum-sum-bst-in-binary-tree/

题目大意：给一颗二叉树，求子树和最大的二叉查找子树的子树和

题目分析：首先要知道如何根据子树信息判断当前树是不是二叉查找树，子树根大于左子树的最大值且小于右子树的最小值，且左右子树都为二叉查找树，于是递归思路很清楚，每次需要返回当前子树的最大最小值和根判断即可，注意空子树可以用一个常量定义（空子树也属于二叉查找树）

6ms，时间击败87.6%

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int ans = Integer.MIN_VALUE;
    final int[] TEMP = new int[]{Integer.MIN_VALUE, Integer.MAX_VALUE, 0, 1};

    int min3(int a, int b, int c) {
        if (a <= b && a <= c) return a;
        if (b <= a && b <= c) return b;
        return c;
    }
    
    int max3(int a, int b, int c) {
        if (a >= b && a >= c) return a;
        if (b >= a && b >= c) return b;
        return c;
    }
    
    // int[0] -> max, int[1] -> min, int[2] -> sum, int[3] -> isBst?
    public int[] dfs(TreeNode root) {
        if (root.left == null && root.right == null) {
            ans = Math.max(ans, root.val);
            return new int[]{root.val, root.val, root.val, 1};
        }     
        int[] l = root.left != null ? dfs(root.left) : TEMP;
        int[] r = root.right != null ? dfs(root.right) : TEMP;
        int sum = l[2] + r[2] + root.val, isBst = 0;
        if (l[0] < root.val && root.val < r[1] && l[3] == 1 && r[3] == 1) {
            ans = Math.max(ans, sum);
            isBst = 1;
        }
        return new int[]{max3(l[0], r[0], root.val), min3(l[1], r[1], root.val), sum, isBst};
    }

    public int maxSumBST(TreeNode root) {
        dfs(root);
        return ans < 0 ? 0 : ans;
    }
}

可以发现，如果某个子树不是二叉查找树，那么其直系父代肯定都不是，因此可以直接通过返回值来判断子树是不是二叉查找树，如果不满足条件直接返回null

5ms，时间击败99.04%

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int ans = Integer.MIN_VALUE;
    final int[] TEMP = new int[]{Integer.MIN_VALUE, Integer.MAX_VALUE, 0};

    int min2(int a, int b) {
        return a > b ? b : a;
    }
    
    int max2(int a, int b) {
        return a > b ? a : b;
    }
    
    // int[0] -> max, int[1] -> min, int[2] -> sum
    public int[] dfs(TreeNode root) {
        if (root.left == null && root.right == null) {
            ans = Math.max(ans, root.val);
            return new int[]{root.val, root.val, root.val, 1};
        }     
        int[] l = root.left != null ? dfs(root.left) : TEMP;
        int[] r = root.right != null ? dfs(root.right) : TEMP;
        if (!(l != null && r != null && l[0] < root.val && root.val < r[1])) {
            return null;
        }
        int sum = l[2] + r[2] + root.val;
        ans = Math.max(ans, sum);
        return new int[]{max2(r[0], root.val), min2(l[1], root.val), sum};
    }

    public int maxSumBST(TreeNode root) {
        dfs(root);
        return ans < 0 ? 0 : ans;
    }
}