Hard

题目描述

给你一棵以 root 为根的二叉树，请你返回任意子树的最大键值和，条件是该子树也必须是一棵二叉搜索树（BST）。

假设二叉搜索树定义如下：

  • 节点的左子树只包含键值小于节点键值的节点。
  • 节点的右子树只包含键值大于节点键值的节点。
  • 左右子树也必须是二叉搜索树。

示例 1：

输入：root = [1,4,3,2,4,2,5,null,null,null,null,null,null,4,6]
输出：20
解释：键值为 3 的子树是和最大的二叉搜索树。

示例 2：

输入：root = [4,3,null,1,2]
输出：2
解释：键值为 2 的单节点子树是和最大的二叉搜索树。

示例 3：

输入：root = [-4,-2,-5]
输出：0
解释：所有节点都为负值，最大的二叉搜索树为空子树。

提示：

  • 树中节点数目在范围 [1, 4 * 10^4] 内
  • -4 * 10^4 <= Node.val <= 4 * 10^4

解题思路

解题思路

这道题的核心是要找到二叉树中所有 BST 子树，并返回其中节点值之和最大的子树。我们可以用后序遍历的方式来解决。

主要思路：

  1. 后序遍历：先递归处理左右子树，再处理当前节点

  2. 状态设计：对于每个节点，我们需要维护四个信息：

    • isBST：当前子树是否为 BST
    • sum：当前子树的节点值之和
    • minVal：当前子树的最小值
    • maxVal：当前子树的最大值

  3. BST 判断条件：

    • 左右子树都必须是 BST
    • 左子树的最大值 < 当前节点值 < 右子树的最小值

  4. 边界处理：

    • 空节点视为有效的 BST，sum=0
    • 单个节点总是有效的 BST

算法流程：

  • 对于每个节点，先递归获取左右子树的信息
  • 判断以当前节点为根的子树是否为 BST
  • 如果是 BST，计算当前子树的和，更新全局最大值
  • 返回当前节点的状态信息供父节点使用

这种方法一次遍历就能得到结果，时间复杂度为 O(n)。

代码实现

class Solution {
public:
    int maxSum = 0;
    
    struct BSTreeInfo {
        bool isBST;
        int sum;
        int minVal;
        int maxVal;
    };
    
    BSTreeInfo dfs(TreeNode* root) {
        if (!root) {
            return {true, 0, INT_MAX, INT_MIN};
        }
        
        BSTreeInfo left = dfs(root->left);
        BSTreeInfo right = dfs(root->right);
        
        if (left.isBST && right.isBST && 
            left.maxVal < root->val && root->val < right.minVal) {
            int currentSum = left.sum + right.sum + root->val;
            maxSum = max(maxSum, currentSum);
            return {true, currentSum, 
                   min(root->val, left.minVal), 
                   max(root->val, right.maxVal)};
        }
        
        return {false, 0, 0, 0};
    }
    
    int maxSumBST(TreeNode* root) {
        dfs(root);
        return maxSum;
    }
};

class Solution:
    def maxSumBST(self, root: Optional[TreeNode]) -> int:
        self.max_sum = 0
        
        def dfs(node):
            if not node:
                return True, 0, float('inf'), float('-inf')
            
            left_is_bst, left_sum, left_min, left_max = dfs(node.left)
            right_is_bst, right_sum, right_min, right_max = dfs(node.right)
            
            if (left_is_bst and right_is_bst and 
                left_max < node.val < right_min):
                current_sum = left_sum + right_sum + node.val
                self.max_sum = max(self.max_sum, current_sum)
                return (True, current_sum, 
                       min(node.val, left_min), 
                       max(node.val, right_max))
            
            return False, 0, 0, 0
        
        dfs(root)
        return self.max_sum

public class Solution {
    private int maxSum = 0;
    
    public class BSTreeInfo {
        public bool isBST;
        public int sum;
        public int minVal;
        public int maxVal;
        
        public BSTreeInfo(bool isBST, int sum, int minVal, int maxVal) {
            this.isBST = isBST;
            this.sum = sum;
            this.minVal = minVal;
            this.maxVal = maxVal;
        }
    }
    
    private BSTreeInfo DFS(TreeNode root) {
        if (root == null) {
            return new BSTreeInfo(true, 0, int.MaxValue, int.MinValue);
        }
        
        BSTreeInfo left = DFS(root.left);
        BSTreeInfo right = DFS(root.right);
        
        if (left.isBST && right.isBST && 
            left.maxVal < root.val && root.val < right.minVal) {
            int currentSum = left.sum + right.sum + root.val;
            maxSum = Math.Max(maxSum, currentSum);
            return new BSTreeInfo(true, currentSum,
                                Math.Min(root.val, left.minVal),
                                Math.Max(root.val, right.maxVal));
        }
        
        return new BSTreeInfo(false, 0, 0, 0);
    }
    
    public int MaxSumBST(TreeNode root) {
        DFS(root);
        return maxSum;
    }
}

var maxSumBST = function(root) {
    let maxSum = 0;
    
    function dfs(node) {
        if (!node) {
            return [true, 0, Infinity, -Infinity];
        }
        
        const [leftIsBST, leftSum, leftMin, leftMax] = dfs(node.left);
        const [rightIsBST, rightSum, rightMin, rightMax] = dfs(node.right);
        
        if (leftIsBST && rightIsBST && 
            leftMax < node.val && node.val < rightMin) {
            const currentSum = leftSum + rightSum + node.val;
            maxSum = Math.max(maxSum, currentSum);
            return [true, currentSum, 
                   Math.min(node.val, leftMin), 
                   Math.max(node.val, rightMax)];
        }
        
        return [false, 0, 0, 0];
    }
    
    dfs(root);
    return maxSum;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历二叉树的每个节点一次
空间复杂度O(h)递归调用栈的深度，h 为树的高度，最坏情况下为 O(n)