java 解法, 执行用时: 6 ms, 内存消耗: 57.4 MB, 提交时间: 2023-05-20 09:09:00

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private int ans;
    private final int inf = 1 << 30;

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

    private int[] dfs(TreeNode root) {
        if (root == null) {
            return new int[] {1, inf, -inf, 0};
        }
        var l = dfs(root.left);
        var r = dfs(root.right);
        int v = root.val;
        if (l[0] == 1 && r[0] == 1 && l[2] < v && r[1] > v) {
            int s = v + l[3] + r[3];
            ans = Math.max(ans, s);
            return new int[] {1, Math.min(l[1], v), Math.max(r[2], v), s};
        }
        return new int[4];
    }
}

golang 解法, 执行用时: 72 ms, 内存消耗: 26.6 MB, 提交时间: 2023-05-20 09:08:26

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func maxSumBST(root *TreeNode) (ans int) {
	const inf = 1 << 30
	var dfs func(root *TreeNode) [4]int
	dfs = func(root *TreeNode) [4]int {
		if root == nil {
			return [4]int{1, inf, -inf, 0}
		}
		l, r := dfs(root.Left), dfs(root.Right)
		if l[0] == 1 && r[0] == 1 && l[2] < root.Val && root.Val < r[1] {
			s := l[3] + r[3] + root.Val
			ans = max(ans, s)
			return [4]int{1, min(l[1], root.Val), max(r[2], root.Val), s}
		}
		return [4]int{}
	}
	dfs(root)
	return
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

python3 解法, 执行用时: 332 ms, 内存消耗: 68.3 MB, 提交时间: 2023-05-20 09:08:06

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxSumBST(self, root: Optional[TreeNode]) -> int:
        def dfs(root: Optional[TreeNode]) -> tuple:
            if root is None:
                return 1, inf, -inf, 0
            lbst, lmi, lmx, ls = dfs(root.left)
            rbst, rmi, rmx, rs = dfs(root.right)
            if lbst and rbst and lmx < root.val < rmi:
                nonlocal ans
                s = ls + rs + root.val
                ans = max(ans, s)
                return 1, min(lmi, root.val), max(rmx, root.val), s
            return 0, 0, 0, 0

        ans = 0
        dfs(root)
        return ans

java 解法, 执行用时: 6 ms, 内存消耗: 58.4 MB, 提交时间: 2023-05-20 09:07:38

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    static final int INF = 0x3f3f3f3f;
    int res;

    class SubTree {
        boolean isBST;
        int minValue;
        int maxValue;
        int sumValue;

        SubTree(boolean isBST, int minValue, int maxValue, int sumValue) {
            this.isBST = isBST;
            this.minValue = minValue;
            this.maxValue = maxValue;
            this.sumValue = sumValue;
        }
    }

    public int maxSumBST(TreeNode root) {
        res = 0;
        dfs(root);
        return res;
    }

    public SubTree dfs(TreeNode root) {
        if (root == null) {
            return new SubTree(true, INF, -INF, 0);
        }
        SubTree left = dfs(root.left);
        SubTree right = dfs(root.right);

        if (left.isBST && right.isBST && root.val > left.maxValue && root.val < right.minValue) {
            int sum = root.val + left.sumValue + right.sumValue;
            res = Math.max(res, sum);
            return new SubTree(true, Math.min(left.minValue, root.val), Math.max(root.val, right.maxValue), sum);
        } else {
            return new SubTree(false, 0, 0, 0);
        }
    }
}

javascript 解法, 执行用时: 152 ms, 内存消耗: 62.4 MB, 提交时间: 2023-05-20 09:07:20

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
 const INF = 0x3f3f3f3f;
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxSumBST = function(root) {
    const dfs = (root) => {
        if (!root) {
            return new SubTree(true, INF, -INF, 0);
        }
        let left = dfs(root.left);
        let right = dfs(root.right);

        if (left.isBST && right.isBST && root.val > left.maxValue && root.val < right.minValue) {
            const sum = root.val + left.sumValue + right.sumValue;
            res = Math.max(res, sum);
            return new SubTree(true, Math.min(left.minValue, root.val), Math.max(root.val, right.maxValue), sum);
        } else {
            return new SubTree(false, 0, 0, 0);
        }
    }
    let res = 0;
    dfs(root);
    return res;
};

class SubTree {
    constructor(isBST, minValue, maxValue, sumValue) {
        this.isBST = isBST;
        this.minValue = minValue;
        this.maxValue = maxValue;
        this.sumValue = sumValue;
    }
}

golang 解法, 执行用时: 100 ms, 内存消耗: 18.2 MB, 提交时间: 2023-05-20 09:06:50

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
const INF = 0x3f3f3f3f
type SubTree struct {
    IsBST bool
    MinVal int
    MaxVal int
    SumVal int
}
var res int

func maxSumBST(root *TreeNode) int {
    res = 0
    dfs(root)
    return res
}

func max(a int, b int) int {
    if a > b {
        return a
    }
    return b
}

func min(a int, b int) int {
    if a < b {
        return a
    }
    return b
}

func dfs(root *TreeNode) *SubTree {
    if root == nil {
        return &SubTree{true, INF, -INF, 0}
    }
    left := dfs(root.Left)
    right := dfs(root.Right)

    if left.IsBST && right.IsBST && root.Val > left.MaxVal && root.Val < right.MinVal {
        sum := root.Val + left.SumVal + right.SumVal
        res = max(res, sum)
        return &SubTree{true, min(left.MinVal, root.Val), max(root.Val, right.MaxVal), sum}
    } else {
        return &SubTree{false, 0, 0, 0}
    }
}

python3 解法, 执行用时: 448 ms, 内存消耗: 71.7 MB, 提交时间: 2023-05-20 09:06:30

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class SubTree:
    def __init__(self, is_bst, min_value, max_value, sum_value):
        self.is_bst = is_bst
        self.min_value = min_value
        self.max_value = max_value
        self.sum_value = sum_value

class Solution:
    INF = 0x3f3f3f3f

    def maxSumBST(self, root: Optional[TreeNode]) -> int:
        self.res = 0
        self.dfs(root)
        return self.res

    def dfs(self, root):
        if root is None:
            return SubTree(True, self.INF, -self.INF, 0)

        left = self.dfs(root.left)
        right = self.dfs(root.right)

        if left.is_bst and right.is_bst and root.val > left.max_value and root.val < right.min_value:
            sum = root.val + left.sum_value + right.sum_value
            self.res = max(self.res, sum)
            return SubTree(True, min(left.min_value, root.val), max(root.val, right.max_value), sum)
        else:
            return SubTree(False, 0, 0, 0)