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

给你一棵以 root 为根的 二叉树 ，请你返回 任意 二叉搜索子树的最大键值和。

func maxSumBST(root *TreeNode) int {
    var maxSum int = int(math.Inf(-1))
    // 判断当前节点是否合法 最小值 最大值 数值和
    var traverse func(root *TreeNode) (isBST bool, min, max *TreeNode, sum int)
    traverse = func(root *TreeNode) (isBST bool, min, max *TreeNode, sum int) {
        if root == nil {
            return true, nil, nil, 0
        }
        if root.Left == nil && root.Right == nil {
            if root.Val > maxSum {
                maxSum = root.Val
            }
            return true, root, root, root.Val
        }
        // left, right, current
        isBST_l, min_l, max_l, sum_l := traverse(root.Left)
        isBST_r, min_r, max_r, sum_r := traverse(root.Right)
        // 判断是否合法的二叉搜索树
        isBST_c := isBST_l && isBST_r
        if max_l != nil && root.Val <= max_l.Val {
            isBST_c = false
        }
        if min_r != nil && root.Val >= min_r.Val {
            isBST_c = false
        }
        if !isBST_c {
            return false, nil, nil, 0
        }
        // 更新 maxSum
        if sum_l+sum_r+root.Val > maxSum {
            maxSum = sum_l + sum_r + root.Val
        }
        // 返回新的值
        var min_c, max_c *TreeNode = min_l, max_r
        if min_l == nil {
            min_c = root
        }
        if max_r == nil {
            max_c = root
        }
        return true, min_c, max_c, sum_l + sum_r + root.Val
    }
    traverse(root)
    if maxSum < 0 {
        return 0
    }
    return maxSum
}

美团面试官：你对后序遍历一无所知 :: labuladong 的算法小抄 (gitee.io)

后序遍历，一次遍历多个返回值，从而解决多个问题。

因为判断合法 BST 需要左右子树的值，获取当前子树的和需要左右子树的值，这两件事可以放在一个后序遍历里面来做。