前言

LeetCode 700：二叉搜索树中的搜索
LeetCode 701：二叉搜索树的插入操作
LeetCode 450：删除二叉搜索树中的节点
LeetCode 108：将有序数组转换成二叉搜索树

一、什么是二叉搜索树

1、空树是二叉搜索树

2、若不为空则应具有以下3条性质：

若它的左子树不为空，则左子树上所有节点的值均小于它的根节点的值；
若它的右子树不为空，则右子树上所有节点的值均小于它的根节点的值；
它的左右子树也均为二叉搜索树.

前提：二叉搜索树首先是一个二叉树。

二、二叉搜索树的操作

1.查找（递归查找是否存在key值）

LeetCode 700题：二叉搜索树中的搜索

给定二叉搜索树（BST）的根节点和一个值。你需要在BST中找到节点值等于给定值的节点。返回以该节点为根的子树。如果节点不存在，则返回 NULL。

例如，

给定二叉搜索树:

和值: 2

你应该返回如下子树:

2     
 / \   
1   3

在上述示例中，如果要找的值是 5，但因为没有节点值为 5，我们应该返回 NULL。

（1）解题思路：

本题首先根据给定的根节点查找到目标节点key：二叉搜索树中的查找不需要遍历所有节点，二叉搜索树是一棵排序树，其中序遍历的结果是一个从小到大排序的数组，故在二叉搜索树中查找某个key值只需要搜索一条路径。

然后返回查找到的节点，完毕。

（2）代码如下：

class Solution {
public:
    TreeNode* traversal(TreeNode* cur,int val){
        if(cur==NULL) return NULL;//终止程序的条件
        if(cur->val>val){//若当前节点的值>val,则说明val存在于当前节点的左子树中，故需要向左查找
            return searchBST(cur->left,val);
        }else if(cur->val<val){//若当前节点的值<val,则说明val存在于当前节点的右子树中，故需要向右查找
            return searchBST(cur->right,val);
        }else{//若当前节点的值==val，则返回当前节点
            return cur;
        }
    }
    TreeNode* searchBST(TreeNode* root, int val) {
        return traversal(root,val);
    }
};

举例说明：

给定二叉搜索树:

和值: 2

若需要找到其树中值为2的节点，只需要从根节点向左查找到值为2节点即可，不需要向右查找，因为根节点右子树上节点的值均大于根节点的值，故对于二叉搜索树的查找操作只需要搜索一条路径，不需要遍历整棵树。

（3）递归步骤（以上述例子为例）:

当 cur==root 时为0层，递归函数 traversal 执行到 return searchBST(cur->left,val); 进入1层递归；
当 cur==root->left 时为1层，递归函数 traversal 执行到 return cur; 得到了1层递归的返回值cur（cur为root->left），此时递归函数进入0层；
此时 cur==root 为0层，只有0层时的return才会结束递归函数。

（4）注意：

具有返回值的递归函数要牢记递归函数定义以及递归函数返回值是什么，在本题中递归函数的定义是：

找到值等于val的节点（所以 return searchBST(cur->left,val); 表示程序最终返回了值为val的节点，实际上函数到达0层的这条语句就结束了）

递归函数的返回值是什么：

若能找到节点，则返回值为值等于val的节点；
若不能找到节点，则返回值为NULL节点。

2.插入（原树中不存在key，插入key）

LeetCode 701：二叉搜索树的插入操作

给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。返回插入后二叉搜索树的根节点。输入数据保证，新值和原始二叉搜索树中的任意节点值都不同。

注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。你可以返回任意有效的结果。

示例 1：

二叉搜索树（LeetCode相关题解（递归求解））前言一、什么是二叉搜索树二、二叉搜索树的操作

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

输出：[4,2,7,1,3,5]

示例 2：

输入：root = [40,20,60,10,30,50,70], val = 25

输出：[40,20,60,10,30,50,70,null,null,25]

示例 3：

输入：root = [4,2,7,1,3,null,null,null,null,null,null], val = 5

输出：[4,2,7,1,3,5]

（1）解题思路：

本题首先需要找到需要插入节点的位置，根据二叉搜索树的有序性很容易找到，关键是怎么处理需要插入的节点（如何将节点插入到指定位置），很显然本题可用递归求解，那么递归函数如何去写，需要回答以下2个问题。

递归函数如何定义
递归函数的返回值是什么

回答：

1、本题的目的是为了将给定数值val插入到二叉搜索树中，故递归函数应定义为将值为val的节点插入树中

2、递归函数的返回值是什么

若当前节点为NULL，则返回新节点
若当前节点不为NULL，则返回含有新节点的树

（2）代码如下：

class Solution {
public:
    TreeNode* traversal(TreeNode* cur,int val){
        //递归函数的定义是将值为val的节点插入树中
        //递归函数返回值的是含有新节点的树
        if(cur==NULL){//返回新节点
            TreeNode* newNode=new TreeNode(val);
            return newNode;
        }
        if(cur->val<val){
            cur->right=traversal(cur->right,val);//将含有新节点的子树插入树中
        }else if(cur->val>val){
            cur->left=traversal(cur->left,val);
        }
        return cur;//返回含有新节点的树
    }
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        return traversal(root,val);
    }
};

（3）递归步骤（以示例1为例）：

二叉搜索树（LeetCode相关题解（递归求解））前言一、什么是二叉搜索树二、二叉搜索树的操作

当cur==root时为0层，递归函数 traversal 执行到 cur->right=traversal(cur->right,val); 进入1层递归；
此时cur==root->right为1层，递归函数 traversal 执行到 cur->left=traversal(cur->left,val); 进入2层递归；
此时cur==root->right->left为2层，递归函数执行到 return newNode; 返回到1层递归；
此时cur==root->right为1层，执行复制操作使得cur->left为newNode，递归函数继续执行到 return cur; 返回到0层；
此时cur==root为0层，并且cur->right->left为newNode。

3.删除（删除树中节点，使得删除后仍为二差搜索树）

LeetCode 450：删除二叉搜索树中的节点

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

一般来说，删除节点可分为两个步骤：

首先找到需要删除的节点；
如果找到了，删除它。

说明：要求算法时间复杂度为 O(h)，h 为树的高度。

示例:

root = [5,3,6,2,4,null,7]

key = 3

给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。

一个正确的答案是 [5,4,6,2,null,null,7]

（1）解题思路：

本题首先需要找到需要删除节点的位置，根据二叉搜索树的有序性很容易找到，要注意的是要删除的节点有以下3种情况：

该节点为叶子节点，只需要将此节点删除即可；
该节点只有左孩子或只有有孩子，若只有左孩子，需将左孩子赋给该节点，若只有右孩子，需将右孩子赋给该节点；
该节点既有左孩子又有右孩子，设该节点右孩子节点为当前节点，不断向下找到当前节点的左孩子节点，直到当前节点的左孩子为NULL，再将该节点的左孩子赋值给当前节点的左孩子，最后将该节点右孩子赋值给该节点。

举例

在题目给出的示例中为第3种情况，要删除节点为值为3的节点，需找到值为3节点的右孩子节点（值为4的节点）将其设为当前节点，不断向下找到当前节点的左孩子节点，由于值为4的节点左孩子为NULL，故将值为3的节点的左孩子节点（值为2的节点）赋值给值为4的节点的左孩子。

结果如下：

递归函数的定义和返回值：

1、递归函数应定义为删除值为val的节点

2、递归函数的返回值是返回删除节点后的树

（2）代码如下：

class Solution {
public:
    TreeNode* traversal(TreeNode* cur,int key){
        //1.删除节点为叶子节点
        //2.删除节点为其他节点，分为
        //(1)仅有左或右子树的节点
        //(2)左右子树均有的节点
        if(cur==NULL) return NULL;
        if(cur->val==key){
            if(cur->left==NULL && cur->right==NULL){
                return NULL;//当前节点无左右孩子直接返回空（将当前节点删除即为空树）
            }else if(cur->left==NULL && cur->right!=NULL){
                return cur->right;//无左孩子有右孩子返回右孩子
            }else if(cur->left!=NULL && cur->right==NULL){
                return cur->left;//无右孩子有左孩子返回左孩子
            }else if(cur->left!=NULL && cur->right!=NULL){
                TreeNode* newNode=cur;//见上述删除节点的第3种情况
                cur=cur->right;
                while(cur->left!=NULL){
                    cur=cur->left;
                }
                cur->left=newNode->left;
                TreeNode* tmp=newNode;
                newNode=newNode->right;
                delete tmp;
                return newNode;
            }
        }
        if(cur->val>key) cur->left=traversal(cur->left,key);//递归函数为返回删除节点之后的树（有则删，没有不删）
        if(cur->val<key) cur->right=traversal(cur->right,key);//递归函数为返回删除节点之后的树（有则删，没有不删）
        return cur;
    }
    TreeNode* deleteNode(TreeNode* root, int key) {
        return traversal(root,key);
    }
};

（3）递归步骤（以本题示例为例）：

删除值为3的节点

当cur==root时为0层，递归函数traversal执行到 cur->left=traversal(cur->left,key); 进入1层；
此时cur==root->left时为1层，此时递归函数traversal执行 if(cur->left!=NULL && cur->right!=NULL) 中的内容，执行到 return newNode; 返回删除节点之后的树，返回0层；
此时cur==root，并且cur->left为newNode（删除节点之后的子树）；

4.构造（递归插入节点）

LeetCode 108：将有序数组转换成二叉搜索树

给你一个整数数组 nums ，其中元素已经按升序排列，请你将其转换为一棵高度平衡二叉搜索树。

高度平衡二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

示例 1：

二叉搜索树（LeetCode相关题解（递归求解））前言一、什么是二叉搜索树二、二叉搜索树的操作

输入：nums = [-10,-3,0,5,9]

输出：[0,-10,5,null,-3,null,9]

（1）解题思路：

本题旨在根据给定的有序数组构造一棵高度平衡的二叉搜索树，所以必然要遍历整棵树，且每次取中间元素进行构造。是因为要保持高度平衡，就要满足每个节点左右子树高度绝对值差小于等于1，那么左右子树节点个数绝对值差需小于等于1。本题递归的思路采用前序遍历的思路，每次构造一个中间节点，再向左向右遍历。

递归函数的定义和返回值：

1、递归函数应定义为前序遍历

2、递归函数的返回值是返回一棵高度平衡的二叉树

（2）代码如下：

class Solution {
public:
    TreeNode* traversal(vector<int>& nums){
        if(nums.size()==0) return NULL;
        int mid=(nums.size()-1)/2;
        TreeNode* root=new TreeNode(nums[mid]);
        vector<int> leftNums(nums.begin(),nums.begin()+mid);
        vector<int> rightNums(nums.begin()+mid+1,nums.end());
        root->left=traversal(leftNums);
        root->right=traversal(rightNums);
        return root; 
    }
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return traversal(nums);
    }
};

（3）递归步骤（以本题示例为例）：

当nums[mid]为0时为0层，root值为0，递归函数执行到 root->left=traversal(leftNums); 时进入1层；
此时nums[mid]为-10为1层，root->left值为-10，递归函数执行到 root->left=traversal(leftNums); 时进入2层；
由于此时leftNums为空，故返回1层；
此时nums[mid]为-10为1层，root->left->right值为-10，递归函数执行到 root->right=traversal(rightNums); 时进入2层；
由于此时leftNums以及rightNums均为空，返回1层；
此时nums[mid]为5时为1层，root->right值为5，递归函数执行到 root->right=traversal(rightNums); 时进入2层；
由于此时leftNums为空，故返回1层；
此时nums[mid]为9为1层，root->right->right值为9，递归函数执行到 root->right=traversal(rightNums); 时进入2层；
由于此时leftNums以及rightNums均为空，返回1层；
此时nums[mid]为5时为1层，递归函数执行到 return root; 返回0层；
当nums[mid]为0时为0层，递归函数执行到 return root; 跳出循环。

参考文献：

[1]: https://leetcode-cn.com/problemset/all/

[2]: https://mp.weixin.qq.com/s/weyitJcVHBgFtSc19cbPdw

二叉搜索树（LeetCode相关题解（递归求解））前言一、什么是二叉搜索树二、二叉搜索树的操作

前言

一、什么是二叉搜索树

二、二叉搜索树的操作

1.查找（递归查找是否存在key值）

LeetCode 700题：二叉搜索树中的搜索

（1）解题思路：

（2）代码如下：

（3）递归步骤（以上述例子为例）:

（4）注意：

2.插入（原树中不存在key，插入key）

LeetCode 701：二叉搜索树的插入操作

（1）解题思路：

（2）代码如下：

（3）递归步骤（以示例1为例）：

3.删除（删除树中节点，使得删除后仍为二差搜索树）

LeetCode 450：删除二叉搜索树中的节点

（1）解题思路：

（2）代码如下：

（3）递归步骤（以本题示例为例）：

4.构造（递归插入节点）

LeetCode 108：将有序数组转换成二叉搜索树

（1）解题思路：

（2）代码如下：

（3）递归步骤（以本题示例为例）：

继续阅读