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

/*
题目思路：
1. 使用后序遍历遍历二叉树，以便处理每个节点时先处理其子节点。
2. 对于每个节点，计算其作为二叉搜索树的可能性，包括最大和。
3. 返回所有可能二叉搜索树的最大和。
使用 Java Stream 的方法。
*/

import java.util.Optional;
import java.util.stream.Stream;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    private class Result {
        int min, max, sum;
        boolean isBST;
        Result(int min, int max, int sum, boolean isBST) {
            this.min = min;
            this.max = max;
            this.sum = sum;
            this.isBST = isBST;
        }
    }

    private int maxSum = 0;

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

    private Result postOrder(TreeNode node) {
        if (node == null) return new Result(Integer.MAX_VALUE, Integer.MIN_VALUE, 0, true);

        Result left = postOrder(node.left);
        Result right = postOrder(node.right);

        if (left.isBST && right.isBST && node.val > left.max && node.val < right.min) {
            int sum = node.val + left.sum + right.sum;
            maxSum = Math.max(maxSum, sum);
            return new Result(Math.min(node.val, left.min), Math.max(node.val, right.max), sum, true);
        } else {
            return new Result(0, 0, 0, false);
        }
    }

    public Stream<TreeNode> stream(TreeNode root) {
        if (root == null) return Stream.empty();
        return Stream.concat(Stream.of(root), Stream.concat(stream(root.left), stream(root.right)));
    }
}