深度优先遍历 DFS
解题思路
从下往上，后序遍历求解；
本题关键点在于判断一棵子树是否是 BST；
BST = 左子树是 BST && 右子树是 BST && 左子树最大值 < 根结点值 && 右子树最小值 >= 根结点值；
复杂度
-
时间复杂度：
O(n)，n 是二叉树结点数目，每个结点只需被遍历一次； -
空间复杂度：
O(h)，h 是二叉树的高度，递归需要是用栈，栈的深度取决于二叉树的高度；
代码实现
var maxSumBST = function (root) {
let dfs = (root) => {
if (root == null) return {
isBST: true, // 返回以 root 为根的二叉树是不是 BST 如果是的话则为 true 否则为 false
min: Infinity, // 返回以 root 为根的这棵 BST 的最小值
max: -Infinity, // 返回以 root 为根的这棵 BST 的最大值
sum: 0, // 返回以 root 为根的这棵 BST 所有节点之和
};
// 递归计算左右子树
let left = dfs(root.left);
let right = dfs(root.right);
if (left.isBST && right.isBST && root.val > left.max && root.val < right.min) {
// 计算以 root 为根的这棵 BST 所有节点之和
let sum = left.sum + right.sum + root.val;
maxSum = Math.max(sum, maxSum);
return {
// 以 root 为根的二叉树是 BST
isBST: true,
// 计算以 root 为根的这棵 BST 的最小值
min: Math.min(left.min, root.val),
// 计算以 root 为根的这棵 BST 的最大值
max: Math.max(right.max, root.val),
sum,
};
} else {
// 以 root 为根的二叉树不是 BST
return { isBST: false };
}
};
let maxSum = 0;
dfs(root);
return maxSum;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 82. 删除排序链表中的重复元素 II
上一篇
评论
