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

Problem: 1373. 二叉搜索子树的最大键值和

思路

解决这个问题的关键在于采用深度优先搜索（DFS）策略，并结合树形动态规划的思想。我们需要设计一个递归函数，它不仅能够遍历整棵树，还能收集到每个子树是否为BST的信息、该子树的最大值、最小值、总和以及最重要的是，以该节点为根的BST所能得到的最大键值和。

解题方法

我提出的解题方法是通过定义一个辅助类Info，用来存储递归过程中需要传递的五个关键信息：当前子树的最大值、最小值、作为BST时的最大键值和、子树的总和以及该子树是否为BST的布尔标记。递归函数f(TreeNode x)负责计算以x为根的子树的各种信息，并返回一个Info对象。

复杂度

时间复杂度:

$O(n)$，每个节点被访问一次，其中n是树中的节点数。

空间复杂度:

$O(n)$，递归调用栈的深度在最坏情况下会达到树的高度，即n（对于极端不平衡的树），但平均情况下要小得多。

Code

/*** 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 {public class Info{public int max;public int min;public int maxBstSum;public int sum;public boolean isBst;public Info(int max, int min, int maxBstSum, int sum, boolean isBst) {this.max = max;this.min = min;this.maxBstSum = maxBstSum;this.sum = sum;this.isBst = isBst;}}public int maxSumBST(TreeNode root) {return f(root).maxBstSum;}public Info f(TreeNode x) {if(x == null) {return new Info(Integer.MIN_VALUE, Integer.MAX_VALUE, 0, 0, true);}Info infol = f(x.left);Info infor = f(x.right);int max = Math.max(x.val, Math.max(infol.max, infor.max));int min = Math.min(x.val, Math.min(infol.min, infor.min));int sum = infol.sum + infor.sum +x.val;boolean isBst = infol.isBst && infor.isBst && infol.max < x.val && x.val < infor.min;int maxBstSum = Math.max(infol.maxBstSum, infor.maxBstSum);if(isBst) {maxBstSum = Math.max(maxBstSum, sum);}return new Info(max, min, maxBstSum, sum, isBst);}
}