C++二叉搜索树代码

代码一，对应力扣二叉搜索树中的检索，代码见下

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* searchBST(TreeNode* root, int val) {if(root == NULL){return NULL;}if(root->val < val){return searchBST(root->right, val);}else if(root->val > val){return searchBST(root->left, val);}else{return root;}}
};

代码二，对应力扣 二叉搜索树的范围和，代码见下

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int rangeSumBST(TreeNode* root, int low, int high) {if(root == NULL){return 0;}int sum = 0;if(root->val >= low && root->val <= high){sum += root->val;}sum += rangeSumBST(root->left, low, high);sum += rangeSumBST(root->right, low, high);return sum;}
};

代码三，将有序数组转化为二叉搜索树，代码见下：

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {TreeNode* sortArray(vector<int>& nums, int l, int r){if(l > r){return NULL;}int mid = (l + r)/2;TreeNode* node = new TreeNode(nums[mid]);node->left = sortArray(nums, l, mid-1);node->right = sortArray(nums, mid+1, r);return node;}
public:TreeNode* sortedArrayToBST(vector<int>& nums) {return sortArray(nums, 0, nums.size()-1);}
};

代码四，对应力扣 验证二叉搜索树，代码见下

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {vector<int> ret;void inOrder(TreeNode* root){if(root){inOrder(root->left);ret.push_back(root->val);inOrder(root->right);}}public:bool isValidBST(TreeNode* root) {ret.clear();inOrder(root);for(int i=1; i<ret.size(); ++i){if(ret[i] < ret[i-1]){return false;}}return true;}
};