二叉搜索子树的最大键值和【LC1373】
给你一棵以 root 为根的 二叉树 ，请你返回 任意 二叉搜索子树的最大键值和。
二叉搜索树的定义如下：
- 任意节点的左子树中的键值都 小于 此节点的键值。
- 任意节点的右子树中的键值都 大于 此节点的键值。
- 任意节点的左子树和右子树都是二叉搜索树。
思路
如果以某一节点为根的子树为二叉搜索树，那么更新结果为该子树之和与目前结果的较大值。
- 如何判断该子树是否是二叉搜索树？必须满足以下条件
- 左子树中的最大值小于该节点值
- 右子树中的最小值大于该节点值
- 因此子树需要返回的信息包括当前子树的所有节点权值之和、当前子树的最小节点值和最大节点值
- 使用树形dp的思想实现
实现
class Solution { private int ans; // 二叉搜索树可以为空 public int maxSumBST(TreeNode root) { dfs(root); return ans; } private int[] dfs(TreeNode node) { if (node == null) return new int[]{Integer.MAX_VALUE, Integer.MIN_VALUE, 0}; int[] left = dfs(node.left); // 递归左子树 int[] right = dfs(node.right); // 递归右子树 int x = node.val; if (x <= left[1] || x >= right[0]) // 不是二叉搜索树 return new int[]{Integer.MIN_VALUE, Integer.MAX_VALUE, 0}; int s = left[2] + right[2] + x; // 这棵子树的所有节点值之和 ans = Math.max(ans, s); return new int[]{Math.min(left[0], x), Math.max(right[1], x), s}; } } 作者：灵茶山艾府 链接：https://leetcode.cn/problems/maximum-sum-bst-in-binary-tree/solutions/2276783/hou-xu-bian-li-pythonjavacgo-by-endlessc-gll3/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
复杂度
- 时间复杂度：O(n)
- 空间复杂度：O(n)
