leetcode 700 二叉搜索树中的搜索

喜欢ヅ旅行 2022-09-12 03:55 175阅读 0赞

## 前言 ##

题目：[700. 二叉搜索树中的搜索][700.]

参考题解：[二叉搜索树中的搜索-代码随想录][-]

--------------------

## 提交代码 ##

二叉搜索树是一个有序树：

*  若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
 *  若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
 *  它的左、右子树也分别为二叉搜索树

题目只要求完成二叉搜索树中查找元素。我顺带实现了二叉搜索树的建立和遍历。关于删除操作，我暂时不知道如何实现。当进程运行结束时，自动释放所有空间，故没有实现二叉树的释放。

#include <iostream>
    #include <vector>
    
    using namespace std;
    
    
    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 Tree {
    private:
        TreeNode* root=nullptr;
    public:
        Tree(vector<int>& nums){
            buildTree(nums);
        }
    
        void insertNode(int val){
            if(root == nullptr){
                root = new TreeNode(val);
                return;
            }
    
            TreeNode* node = root;
            while(1){
                if(val == node->val)
                    break;
                else if(val < node->val && node->left == nullptr){
                    node->left = new TreeNode(val);
                    break;
                }else if(val < node->val && node->left != nullptr){
                    node = node->left;
                }else if(val > node->val && node->right == nullptr){
                    node->right = new TreeNode(val);
                    break;
                }else if(val > node->val && node->right != nullptr){
                    node = node->right;
                }
            }
        }
    
        void buildTree(vector<int>& nums){
            for(auto num : nums)
                insertNode(num);
        }
    
        void inorderTraverse(TreeNode* root,vector<int>& result){
            if(root == nullptr)
                return;
            inorderTraverse(root->left,result);
            result.push_back(root->val);
            inorderTraverse(root->right,result);
        }
    
        TreeNode* getRoot(void){
            return root;
        }
    };
    
    
    class Solution {
    public:
        TreeNode* searchBST(TreeNode* root, int val) {
            if(root == nullptr)
                return nullptr;
            if(val == root->val)
                return root;
            if(val < root->val)
                return searchBST(root->left,val);
            // if(val > root->val)
            //     return searchBST(root->right,val);
            return searchBST(root->right,val);
        }
    };
    
    int main(void){
        vector<int> nums = {4,2,7,1,3};
        Tree tree(nums);
        Solution s;
        TreeNode* result = s.searchBST(tree.getRoot(),nums[1]);
        if(result == nullptr)
            cout<<"error:cant find..."<<endl;
        else
            cout<<"find "<<nums[1]<<endl;
        return 0;
    }

关于二叉搜索树的查找操作，也可通过迭代实现。下面代码来自参考题解。

class Solution {
    public:
        TreeNode* searchBST(TreeNode* root, int val) {
            while (root != NULL) {
                if (root->val > val) root = root->left;
                else if (root->val < val) root = root->right;
                else return root;
            }
            return NULL;
        }
    };

[700.]: https://leetcode-cn.com/problems/search-in-a-binary-search-tree/
[-]: https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0700.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E6%90%9C%E7%B4%A2.md