https://leetcode.com/problems/maximum-sum-bst-in-binary-tree/

maximum-sum-bst-in-binary-tree.java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int max;
    public int maxSumBST(TreeNode root) {
        if (root == null) {
            return 0;
        }
        this.max = 0;
        search(root);
        return this.max;
    }
    
    public int[] search(TreeNode node) {
        int bst = 1;
        int min = node.val;
        int max = node.val;
        int sum = node.val;
        // handle left
        if (node.left != null) {
            int[] fromLeft = search(node.left);
            if (fromLeft[0] == -1 || fromLeft[2] >= node.val) {
                bst = -1;
            } else {
                min = fromLeft[1];
                sum += fromLeft[3];
            }
        }
    
        // handle right
        if (node.right != null) {
            int[] fromRight = search(node.right);
            if (fromRight[0] == -1 || fromRight[1] <= node.val) {
                bst = -1;
            } else {
                 max = fromRight[2];
                 sum += fromRight[3];
            }
        }
        //System.out.println("node: " + node.val + "\tmin: " + min + "\tmax: " + max + "\tsum: " + sum);
        if (bst == 1) this.max = Math.max(this.max, sum);
        return new int[]{bst, min, max, sum};
    }
}