小黑马拉松后第三天，腿跑步的疼痛好多了的leetcode之旅:1373. 二叉搜索子树的最大键值和

阅读：评论：0

递归法(Python)

# 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:self.max_sum = 0# 递归函数def dfs(node):# 结点为空，算是二叉搜索树if not node:return {'is_balance':True,'max':-inf,'min':inf,'sum':0}result1 = dfs(node.left)result2 = dfs(node.right)# 孩子结点是否为二叉搜索树，新加入的根节点是否符合要求if not (result1['is_balance'] and result2['is_balance'] and node.val > result1['max'] and node.val < result2['min']):return {'is_balance':False,'max':0,'min':0,'sum':0}# 求得最值c_min = result1['min'] if node.left else node.valc_max = result2['max'] if node.right else node.valsum_ = result1['sum'] + result2['sum'] + node.valif sum_ > self.max_sum:self.max_sum = sum_return {'is_balance':True,'max':c_max,'min':c_min,'sum':sum_}dfs(root)return self.max_sum

递归法(Java)

/*** 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 {int max_sum = 0;public int maxSumBST(TreeNode root) {dfs(root);return this.max_sum;}public int[] dfs(TreeNode node){int[] result = new int[4];if(node == null){result[0] = 1;result[1] = Integer.MAX_VALUE;result[2] = Integer.MIN_VALUE;result[3] = 0;return result;}int[] result1 = dfs(node.left);int[] result2 = dfs(node.right);if(result1[0] == 0 || result2[0] == 0 || result1[2] >= node.val || result2[1] <= node.val){return result;}result[0] = 1;result[1] = node.left!=null ? result1[1]:node.val;result[2] = node.right!=null ? result2[2]:node.val;result[3] = result1[3] + result2[3] + node.val;if(result[3] > this.max_sum){this.max_sum = result[3];}return result;}
}