Untitled

 avatar
unknown
plain_text
a month ago
1.1 kB
3
Indexable
class Solution {
    private int maxSum = 0;

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

    private int[] dfs(TreeNode node) {
        // Base case: Null node
        if (node == null) return new int[] {1, Integer.MAX_VALUE, Integer.MIN_VALUE, 0}; // {isBST, min, max, sum}

        // Postorder traversal: Process left and right subtrees first
        int[] left = dfs(node.left);
        int[] right = dfs(node.right);

        // Check if current node forms a BST
        if (left[0] == 1 && right[0] == 1 && node.val > left[2] && node.val < right[1]) {
            int sum = node.val + left[3] + right[3];
            maxSum = Math.max(maxSum, sum); // Update global maximum sum

            // Return values for this subtree
            int minVal = Math.min(node.val, left[1]);
            int maxVal = Math.max(node.val, right[2]);
            return new int[] {1, minVal, maxVal, sum};
        }

        // If not a BST, return invalid result
        return new int[] {0, 0, 0, 0};
    }
}
Leave a Comment