leetcode-1373 二叉搜索子树的最大键值和

题目描述：给你一棵以 root 为根的 二叉树 ，请你返回 任意 二叉搜索子树的最大键值和。

二叉搜索树的定义如下：

• 任意节点的左子树中的键值都 小于 此节点的键值。
• 任意节点的右子树中的键值都 大于 此节点的键值。
• 任意节点的左子树和右子树都是二叉搜索树。
• 每棵树有 1 到 40000 个节点。
• 每个节点的键值在 [-4 * 10^4 , 4 * 10^4] 之间。

代码实现

递归实现

class Solution {
    private int maxSum = 0;

    public int maxSumBST(TreeNode root) {
        postBST(root);
        return maxSum;
    }

    /**
     * int[] 是否是二叉搜索树，左子树最小值，右子树最大值，如果是二叉搜索树则求和
     *
     */
    private int[] postBST(TreeNode root) {
        if (root == null) {
            return new int[]{1, Integer.MAX_VALUE, Integer.MIN_VALUE, 0};
        }
        int[] left = postBST(root.left);
        int[] right = postBST(root.right);
        int[] res = new int[]{-1, Integer.MAX_VALUE, Integer.MIN_VALUE, 0};
        if (left[0] == 1 && right[0] == 1 && root.val > left[2] && root.val < right[1]) {
            res[0] = 1;
            res[1] = Math.min(root.val, left[1]);
            res[2] = Math.max(root.val, right[2]);
            res[3] = left[3] + right[3] + root.val;
            maxSum = Math.max(res[3], maxSum);
        }
        return res;
    }
}