Untitled
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