【701. 二叉搜索树中的插入操作中等】

题目：

给定二叉搜索树（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, 104]的范围内。
-108 <= Node.val <= 108
所有值 Node.val 是独一无二的。
-108 <= val <= 108
保证 val 在原始BST中不存在。

思路：

如下演示视频中可以看出：只要按照二叉搜索树的规则去遍历，遇到空节点就插入节点就可以了。
在这里插入图片描述

例如插入元素10 ，需要找到末尾节点插入便可，一样的道理来插入元素15，插入元素0，插入元素6，需要调整二叉树的结构么？并不需要。。

只要遍历二叉搜索树，找到空节点插入元素就可以了，那么这道题其实就简单了。

接下来就是遍历二叉搜索树的过程了。

递归法

递归三部曲：

确定递归函数参数以及返回值

参数就是根节点指针，以及要插入元素，这里递归函数要不要有返回值呢？

可以有，也可以没有，但递归函数如果没有返回值的话，实现是比较麻烦的。

有返回值的话，可以利用返回值完成新加入的节点与其父节点的赋值操作。

递归函数的返回类型为节点类型TreeNode * 。

代码如下：

TreeNode* insertIntoBST(TreeNode* root, int val)

确定终止条件

终止条件就是找到遍历的节点为null的时候，就是要插入节点的位置了，并把插入的节点返回。

代码如下：

if (root == NULL) {TreeNode* node = new TreeNode(val);return node;
}

这里把添加的节点返回给上一层，就完成了父子节点的赋值操作了，详细再往下看。

确定单层递归的逻辑

此时要明确，需要遍历整棵树么？

别忘了这是搜索树，遍历整棵搜索树简直是对搜索树的侮辱。

搜索树是有方向了，可以根据插入元素的数值，决定递归方向。

代码如下：

if (root->val > val) root->left = insertIntoBST(root->left, val);
if (root->val < val) root->right = insertIntoBST(root->right, val);
return root;

到这里，应该能感受到，如何通过递归函数返回值完成了新加入节点的父子关系赋值操作了，下一层将加入节点返回，本层用root->left或者root->right将其接住。

迭代法

在迭代法遍历的过程中，需要记录一下当前遍历的节点的父节点，这样才能做插入节点的操作。

因为迭代的循环退出后，当前节点cur为NULL，且cur的位置就是要插入元素的位置，所以要记录该节点的父节点parent进行赋值。

代码：

递归法

class Solution {
public:TreeNode* insertIntoBST(TreeNode* root, int val) {if(root == NULL){TreeNode* node = new TreeNode(val);return node;}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* insertIntoBST(TreeNode* root, int val) {if(root == NULL){TreeNode* node = new TreeNode(val);return node;}TreeNode* cur = root;   //  当前节点TreeNode* parent = root;    // 这个很重要，需要记录上一个节点，否则无法赋值新节点while(cur != NULL){ //  退出循环后，此时的cur为空，且cur的位置就是插入元素的位置，所以根据cur的父节点parent赋值parent = cur;if(cur->val > val) cur = cur->left;else if(cur->val < val) cur = cur->right;}//  根据parent赋值TreeNode* node = new TreeNode(val);if(parent->val > val) parent->left = node;else parent->right = node;return root;}
};