【从零开始的刷题之旅】二叉搜索树（01）：增删改查

二叉搜索树

二叉搜索树是在二叉树的基础上做了一些有序性的处理。

简单来说就是左子树的所有节点值都小于它的根节点，而右子树的所有节点值都大于它的根节点。

因为这个特性，二叉搜索树有一条非常好用的性质：

中序遍历的结果是有序的，并且是升序。

根据这条性质我们可以解决很多问题。

首先是二叉搜索树的增删改查。

二叉搜索树的增删改查

掌握二叉搜索树的这几种基本操作，就可以解决一系列相关问题。

二叉搜索树的搜索

leetcode 700 二叉搜索树中的搜索

给定值，在二叉搜索树中搜索，返回以该值为根的子树。

我们可以用递归来解决，但是比单纯的递归更好的办法是要结合二叉搜索树的左小右大的特性。

在当前节点值小于给定值时，搜索右子树；当前节点值大于给定值时，搜索左子树。

TreeNode* searchBST(TreeNode* root, int val) {
        if(root==NULL)
            return NULL;
        
        if(root->val==val)
        	return root;
        
        if(root->valright,val);
        if(root->val>val)
            return searchBST(root->left,val);
        
        return NULL;

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

这样可以提高递归的效率。

二叉搜索树的插入

leetcode 701 二叉搜索树中的插入操作

给定二叉搜索