fucking-algorithm
fucking-algorithm copied to clipboard
labuladong
美团面试官：你对后序遍历一无所知 :: labuladong的算法小抄
public static class BSTInfo {
public boolean isBST;
public int maxSum;
public int min;
public int max;}
===> 返回数组是很好的方法，不过如果返回一个自定义对象会更清晰。
// 这个 if 在判断以 root 为根的二叉树是不是 BST
if (left[0] == 1 && right[0] == 1 &&
root.val > left[2] && root.val < right[1]) {
// 以 root 为根的二叉树是 BST
res[0] = 1;
// 计算以 root 为根的这棵 BST 的最小值
res[1] = Math.min(left[1], root.val);
// 计算以 root 为根的这棵 BST 的最大值
res[2] = Math.max(right[2], root.val);
// 计算以 root 为根的这棵 BST 所有节点之和
res[3] = left[3] + right[3] + root.val;
// 更新全局变量
maxSum = Math.max(maxSum, res[3]);
}
在if中已经判断了 root.val大于left子树的最大值left[2]，小于right子树的最小值right[1]。
为什么在判断体内，还要进行它和left子树的最小值比较大小呢，res[1] = Math.min(left[1], root.val);？
如果我们判断以 root 为根的二叉树是 BST，root.val一定大于left[1]吧。
@JackShang94, 这跟我们对空节点的处理有关，我们处理空节点的时候，把它的最小值设成了正无穷，最大值设成了负无穷，如果不比较大小直接赋值的话，那么它们的父亲节点的最小值也变成正无穷了，最大值也变成负无穷了，只有和是对的。也就是说，这会对以非空节点为根的子树的性质产生影响。
@JackShang94, 这跟我们对空节点的处理有关，我们处理空节点的时候，把它的最小值设成了正无穷，最大值设成了负无穷，如果不比较大小直接赋值的话，那么它们的父亲节点的最小值也变成正无穷了，最大值也变成负无穷了，只有和是对的。也就是说，这会对以非空节点为根的子树的性质产生影响。
谢谢解答，茅塞顿开。不进行比较的话，前方代码对空节点的处理确实会影响到其父节点的赋值。
js 版，充分利用了 js 语法的灵活性，让代码更可读：
var maxSumBST = function (root) {
let maxSum = 0;
traverse(root);
return maxSum;
function traverse(node) {
// base case
if (node == null) {
return [true, Infinity, -Infinity, 0];
}
// 递归计算左右子树
const [isLeftBST, leftMin, leftMax, leftSum] = traverse(node.left);
const [isRightBST, rightMin, rightMax, rightSum] = traverse(node.right);
/******* 后序遍历位置 *******/
let isBST = false,
min = 0,
max = 0,
sum = 0;
next: {
// 下面两个 if 在判断以 node 为根的二叉树是不是 BST
if (!isLeftBST || !isRightBST) {
break next;
}
if (node.val <= leftMax || node.val >= rightMin) {
break next;
}
// 以 node 为根的二叉树是 BST
isBST = true;
// 计算以 node 为根的这棵 BST 的最小值
min = Math.min(leftMin, node.val);
// 计算以 node 为根的这棵 BST 的最大值
max = Math.max(rightMax, node.val);
// 计算以 node 为根的这棵 BST 所有节点之和
sum = leftSum + rightSum + node.val;
// 更新全局变量
maxSum = Math.max(maxSum, sum);
}
/**************************/
return [isBST, min, max, sum];
}
};
东哥想问一下，这种解法没有通过解答，是哪里有问题吗 public int maxSumBST(TreeNode root) { // 1、确认这个节点是否为bst // 2、不是bst就跳过，是bst计算这个bst的节点值，与最大节点值对比置换 if (root == null) { return 0; } boolean isBst = isValidBST(root, null, null); if (isBst) { return countVal(root); } int left = maxSumBST(root.left); int right = maxSumBST(root.right); return Math.max(left, right); }
private int countVal(TreeNode root) {
if (root == null) {
return 0;
}
int i = countVal(root.left);
int i1 = countVal(root.right);
int res = root.val + i + i1;
return res > 0 ? res : 0;
}
private boolean isValidBST(TreeNode root, TreeNode min, TreeNode max) {
if (root == null) {
return true;
}
if (min != null && root.val < min.val) {
return false;
}
if (max != null && root.val > max.val) {
return false;
}
return isValidBST(root.left, min, root) &&
isValidBST(root.right, root, max);
}
@anthonyAndchen 题目明确说了“All values are negatives. Return an empty BST.” 所以主函数最后return maxSum之前需要check一下maxSum是不是负数，如果为负则return 0。
按照东哥的解法，写的 Golang 版本，但是时间和内存分别击败 28%、10% 的 Go 提交者，有无懂哥指点为什么？代码如下：
func maxSumBST(root *TreeNode) int {
var MaxSum int =0 // 定义全局变量存储最大值
var traverse func(*TreeNode) [4]int
traverse = func (node *TreeNode) (res [4]int ){
// 1.base case
// res含义：
// res[0] 子树是不是BST 0不是 1是
// res[1] 子树最小值
// res[2] 子树最大值
// res[3] 子树节点值之和
if node==nil{
res=[4]int{1,int(^uint(0) >> 1),^int(^uint(0) >> 1),0}
return res
}
//2.递归遍历左右子树
leftTree := traverse(node.Left)
rightTree := traverse(node.Right)
//3.****************后序遍历的位置*******************//
// 左子树是BST 右子树是BST 节点值大于左子树最大值且小于右子树最小值
if (leftTree[0]==1)&&(rightTree[0]==1)&&(node.Val>leftTree[2] && node.Val<rightTree[1]) {
res[0]=1
res[1]=leftTree[1]
if node.Val<leftTree[1]{
res[1]=node.Val
}
res[2]=rightTree[2]
if node.Val>rightTree[2]{
res[2]=node.Val
}
res[3]=leftTree[3]+rightTree[3]+node.Val
if res[3]>MaxSum{
MaxSum=res[3]
}
}else{
res[0]=0
}
return res
}
traverse(root)
return MaxSum
}
@Carlos9986 golang把闭包换成普通函数， 把返回数组换成多返回值会好很多，以下均击败90+%
var sum int
const INT_MAX = int(^uint(0) >> 1)
const INT_MIN = ^INT_MAX
func max(a, b int) int {
if a > b {
return a
}
return b
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func traverse(root *TreeNode) (isBST bool, curMax int, curMin int, curSum int) {
if root == nil {
// 注意这里返回的值, 当节点为nil时需要保证其父节点能够正确判断为二叉搜索树
return true, INT_MIN, INT_MAX, 0
}
lIsBST, lMax, lMin, lSum := traverse(root.Left)
rIsBST, rMax, rMin, rSum := traverse(root.Right)
isBST = lIsBST && rIsBST && lMax < root.Val && root.Val < rMin
if isBST {
// 设置 max 和 min 函数作用是当左右节点为空时能够正确更新当前的max和min值
curMax = max(root.Val, rMax)
curMin = min(root.Val, lMin)
curSum = lSum + rSum + root.Val
if curSum > sum {
sum = curSum
}
return isBST, curMax, curMin, curSum
}
// 当不为二叉搜索树时计算无意义, 直接返回
return false, 0, 0, 0
}
func maxSumBST(root *TreeNode) int {
// golang判题注意每次进入函数时初始化外部变量, 不然外部变量不会自动归0
sum = 0
traverse(root)
return sum
}
