前言
本文是二叉搜索树操作。
二叉树篇继续。
一、题目阅读
给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。
注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。
示例 1：
输入：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]
提示：
树中的节点数将在 [0, 10^4]的范围内。
-10^8 <= Node.val <= 10^8
所有值 Node.val 是 独一无二 的。
-10^8 <= val <= 10^8
保证 val 在原始BST中不存在。
二、尝试解答
从示例一的图中可以看到，插入一个节点后仍然保持二叉搜索树，方式有很多种。
但是我想用递归实现，那么需要找到一个可以重复的操作。
思路
- 二叉搜索树中序遍历是有序递增的序列，那么插入节点要么插入到该序列最左端，成为新树的最小值；要么在序列中间插入；要么插入到序列的最右端，成为新树的最大值。
- 所以确定中序遍历。找到新节点的插入位置。
- 定一个遍历函数：中序递归操作——
- 确定函数参数：TreeNode*& cur，int val。指针需要加引用，因为是对原树进行操作，如果不加引用，该层实现副本操作，返回上一层对原二叉树没有影响。
- 确定函数返回值：void。因为用指针引用操作，所以直接修改树，不需要返回值。
- 确定中间节点逻辑：
- 如果cur->val中间节点值 > val插入的节点，那么：新建节点newnode——用temp接过原来的左子树——cur->left = newnode——newnode->left = temp。此流程可以保证是二叉搜索树。注意，有问题：因为该逻辑在遍历右子树之前，所以后面递归到右子树，会重复插入很多这个新节点。
- 所以需要pre指针指向前一个节点。再加pre->val < val && cur->val > val。这才能正确插入一个新节点。
- 还没有结束：上面是在序列中间插入；如果插入节点要么插入到该序列最左端呢？pre初始为空，且cur->val > val，说明插入到最左端。
- 如果插入节点要么插入到该序列最右端呢？发现在递归函数中无法解决。只有在主函数里补充这个情况。pre全局变量最后一定指向原来二叉搜索树的最大值，那么在最大值->right = newnode。
- 再发现：如果原二叉树是空，在递归函数中也没有包含，仍然需要在主函数中涵盖。
代码实现
class Solution {
public:
TreeNode* pre = nullptr;
void insert(TreeNode*& cur,int val){//对树本身操作，所以树节点需要是引用形式
if(!cur) return;
insert(cur->left,val);
if((pre &&pre->val < val && cur->val > val) || (!pre && cur->val > val) ){//确定了插入位置，数值在整个树中间或最左边
TreeNode* newnode = new TreeNode(val);//新建节点
TreeNode* temp = cur->left;//先断开下左子树，也包含空
cur->left = newnode;//插入节点
newnode->left = temp;
}
pre = cur;
insert(cur->right,val);
return;
}
TreeNode* insertIntoBST(TreeNode* root, int val) {
if(!root){//空树，补充。
root = new TreeNode(val);
return root;
}
insert(root,val);
if(pre->val < val){//插入节点是最大的，补充最大值。
TreeNode* newnode = new TreeNode(val);
pre->right = newnode;
}
return root;
}
};
所以，该思路按照插入节点在有序序列的位置，分3种情况；还有原树为空的情况。在递归函数中只能涵盖两种，剩下两种在主函数中补充。
三、参考学习
参考学习链接
有没有更统一的递归函数，改进上面的实现？
学习内容
- 思路：插入节点后，新插入节点的位置都可以是叶子结点。当前节点可以指明新插入节点的叶子位置。这个思路更简单。
2.代码实现：
虽然思路简单，但是代码实现上也需要注意——
（1）递归返回值给到上一层的左子树或右子树。遇到空，上一层节点左/右子树接住新建插入节点；
（2）插入之后，再向上层返回，返回的是root自身。
class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int val) {
//终止条件,遇到空的时候，新建节点返回newnode
if(!root) {
TreeNode* newnode = new TreeNode(val);
return newnode;
}
if(root->val > val){
root->left = insertIntoBST(root->left,val);//用左子树接住空的返回值
}else if(root->val < val){
root->right = insertIntoBST(root->right,val);//需要用上一层的节点接住遇到空节点的新建节点
}
return root;
}
};
- 递归不用返回值的函数：
class Solution {
public:
TreeNode* pre = nullptr;
void traversal(TreeNode* cur,int val){
if(!cur){
TreeNode* node = new TreeNode(val);
if(pre->val > val) pre->left = node;
else pre->right = node;
return;
}
pre = cur;
if(cur->val > val){
traversal(cur->left,val);
}else if(cur->val < val){
traversal(cur->right,val);
}
return;
}
TreeNode* insertIntoBST(TreeNode* root, int val) {
if(!root){
root = new TreeNode(val);
return root;
}
traversal(root,val);
return root;
}
};
对比参考代码：
（1）parent = new TreeNode(0);//没有。但是在root判空之后，新建节点，直接return。
- 迭代法，代码实现：
class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int val) {
if(!root){
root = new TreeNode(val);
return root;
}
TreeNode* cur = root;
TreeNode* pre = nullptr;
while(cur){
pre = cur;
if(cur->val > val){
cur = cur->left;
}else if(cur->val < val){
cur = cur->right;
}
}
//退出循环时，cur为空。pre是父节点
TreeNode* node = new TreeNode(val);
if(pre->val > val) pre->left = node;
else pre->right = node;
return root;
}
};
对比参考代码：一样。
总结
【701.二叉搜索树中的插入操作】
（欢迎指正，转载标明出处）