1.LeetCode:938. 二叉搜索树的范围和

原题链接

        给定二叉搜索树的根结点 root，返回值位于范围 [low, high] 之间的所有结点的值的和。

        示例 1：

        输入：root = [10,5,15,3,7,null,18], low = 7, high = 15

        输出：32

        示例 2：

        输入：root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10

        输出：23

        提示：

        树中节点数目在范围 [1, 2 * 1e4] 内

        1 <= Node.val <= 105

        1 <= low <= high <= 105

        所有 Node.val 互不相同

        利用bst的性质在low到high范围内搜索并累加和即可

class Solution {
public:
    int rangeSumBST(TreeNode* root, int low, int high) {
        if(!root){
            return 0;
        }
        if(root->val<low){
            return rangeSumBST(root->right,low,high);
        }
        if(root->val>high){
            return rangeSumBST(root->left,low,high);
        }
        return root->val+rangeSumBST(root->left,low,high)+rangeSumBST(root->right,low,high);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2.LeetCode:剑指 Offer II 054. 所有大于等于节点的值之和

原题链接

3.LeetCode:538. 把二叉搜索树转换为累加树

原题链接

4.LeetCode:1038. 从二叉搜索树到更大和树

原题链接

        给定一个二叉搜索树，请将它的每个节点的值替换成树中大于或者等于该节点值的所有节点值之和。

        提醒一下，二叉搜索树满足下列约束条件：

        节点的左子树仅包含键 小于 节点键的节点。

        节点的右子树仅包含键 大于 节点键的节点。

        左右子树也必须是二叉搜索树。

        示例 1：

        输入：root = [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]

        输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

        示例 2：

        输入：root = [0,null,1]

        输出：[1,null,1]

        示例 3：

        输入：root = [1,0,2]

        输出：[3,3,2]

        示例 4：

        输入：root = [3,2,4,1]

        输出：[7,9,4,10]

        提示：

        树中的节点数介于 0 和 1e4 之间。

        每个节点的值介于 -1e4 和 1e4 之间。

        树中的所有值 互不相同 。

        给定的树为二叉搜索树。

        由于bst的中序序列是一个递增序列，所以我们中序遍历二叉树然后进行后缀和即可

vector<TreeNode*> tmp;
void inorder(TreeNode* root){
    if(!root){
        return ;
    }
    inorder(root->left);
    tmp.push_back(root);
    inorder(root->right);
}
class Solution {
public:
    TreeNode* convertBST(TreeNode* root) {
        tmp.clear();
        inorder(root);
        for(int i=tmp.size()-2;i>=0;--i){
            tmp[i]->val+=tmp[i+1]->val;
        }
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20