【LeetCode每日一题】938. 二叉搜索树的范围和
2024-2-26
938. 二叉搜索树的范围和
思路:
1.在二叉搜索树中:左子树的结点都小于根节点,右子树的结点都大于根节点,每个结点法左右子树均要符合二叉搜索树
2.如果根节点的值大于hight,就排除右树,只在左树中查找
3.如果根节点的值小于low,就排除左树,只在右树中查找
4.如果正好在两者之间,则左树右树都要考虑,将根节点的值和递归的结果累加
写法一:在中间累加
//[938. 二叉搜索树的范围和]-写法二
//
public int rangeSumBST2(TreeNode root, int low, int high) {
if (root==null){
return 0;
}
int x = root.val;
int sum = low<=x && x<=high?x:0;
//根节点的值如果在范围内,返回根节点的值,否则就返回0,相当于排除了不在范围内的值
if(x>low){
sum+=rangeSumBST2(root.left,low,high);
}
if (x<high){
sum+=rangeSumBST2(root.right,low,high);
}
return sum;
}
写法二:在最后累加
//[938. 二叉搜索树的范围和]
public int rangeSumBST(TreeNode root, int low, int high) {
if (root == null) {
return 0;
}
int x = root.val;
if (x > high) {
return rangeSumBST(root.left, low, high);
//右树不在范围内,只需要递归左树
}
if (x < low) {
return rangeSumBST(root.right, low, high);
//左树不在范围内,只需要递归左树
}
return x + rangeSumBST(root.left, low, high) + rangeSumBST(root.right, low, high);
//左右子树都可能
}
原文地址:https://blog.csdn.net/m0_64003319/article/details/136308927
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!