二叉搜索树的范围和

LeetCode-938

首先需要仔细理解题目的意思：找出所有节点值在L和R之间的数的和。
这里采用递归来完成，主要需要注意二叉搜索树的性质。

/**

 * 给定二叉搜索树的根结点 root，返回 L 和 R（含）之间的所有结点的值的和。

 * 二叉搜索树保证具有唯一的值。

 **/

#include<iostream>

#include<cstring>

#include<string>

#include<algorithm>

#include<cstdio>

#include<queue>

#include<vector>

using namespace std;

// Definition for a binary tree node.

struct TreeNode {

    int val;

    TreeNode *left;

    TreeNode *right;

    TreeNode(int x) : val(x), left(NULL), right(NULL) {}

};

/**

       10

     /   \

    5    15

   / \     \

  3  7     18

**/

class Solution {

private:

    int sum=0;//

    int l,r;

public:

    void rangeSum(TreeNode* node){

        //cout<<node->val<<endl;

        if(node->val<=r&&node->val>=l){

            sum+=node->val;

            if(node->left)

                rangeSum(node->left);

            if(node->right)

                rangeSum(node->right);

        }else if(node->val<l){

            if(node->right)

                rangeSum(node->right);

        }else if(node->val>r){

            if(node->left)

                rangeSum(node->left);

        }

    }

    int rangeSumBST(TreeNode* root, int L, int R) {

        this->l=L;

        this->r=R;

        if(root)

            rangeSum(root);

        return sum;

    }

};

int main(){

    TreeNode* t1=new TreeNode(10);

    TreeNode* t2=new TreeNode(5);

    TreeNode* t3=new TreeNode(15);

    TreeNode* t4=new TreeNode(3);

    TreeNode* t5=new TreeNode(7);

    TreeNode* t6=new TreeNode(18);

    t2->left=t4;t2->right=t5;

    t3->left=t6;

    t1->left=t2;t1->right=t3;

    Solution solution;

    cout<<solution.rangeSumBST(t1,7,15)<<endl;

    system("pause");

    return 0;

}

巴特西

LeetCode-二叉搜索树的范围和

二叉搜索树的范围和

LeetCode-938

最新文章

热门文章