声明：问题描述来源leetcode

一、问题描述：

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

难度中等400

给定二叉搜索树（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中不存在。

二、题解：

• 思路：

还是中序遍历，就是在写好中序遍历的基础上不断地进行修修补补.

xin麒的思路一开始是这样的

首先回忆下中序遍历的样子：

• 过程1

public class Solution {public TreeNode insertIntoBST(TreeNode root, int val) {search(root);return root;}private void search(TreeNode root) {if (root.left != null) search(root.left);if (root.right != null) search(root.right);}
}

一开始xin麒觉得只要搜索到刚刚好大于val的时候就将该节点返回，然后就对改节点进行处理不就好了吗？怎么处理？看下面的：

• 过程2

public class Solution {TreeNode goal = new TreeNode(Integer.MIN_VALUE);int val;public TreeNode insertIntoBST(TreeNode root, int val) {if (root == null) return new TreeNode(val);search(root);if (goal.val > val){goal.left = new TreeNode(val);}else {goal.right = new TreeNode(val);}return root;}private void search(TreeNode root) {if (goal.val > val) return;if (root.left != null) search(root.left);goal = root;if (root.right != null) search(root.right);}
}

如果root为空，那么直接返回一个以val为值的树；

①我们要找出一个刚刚好大于val的树节点，那么就要在中间让goal进行赋值。然后当搜索结束后我们就可以将得到的goal做处理。对于返回的节点goal还要处理下，因为可能题目锁给的整棵树的所有值没有比val更大的值。

对于返回来的结果，如果goal.val小于val那么说明整棵树就没有比val更大的节点了。

于是将新节点插入goal的右子树，反正则左子树。

②而为什么初始化goal时是TreeNode goal = new TreeNode(Integer.MIN_VALUE);这样子呢？

因为Integer.MIN_VALUE < -10^8,保证一开始能够进得去递归函数search里面。

• 过程3

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

时的结果应该是下面这样：

但是依据之前的代码的结果是：

为什么呢，因为在search的递归遍历到节点30时，本来是返回30这个节点的，但是因为走完左子树不加控制，导致返回的值不是真正想要的，也就是在if (root.left != null) search(root.left);后没加防控，应该再判断一下goal.val才对，于是应该修改search的方法为：

private void search(TreeNode root) {if (goal.val > val) return;if (root.left != null) search(root.left);if (goal.val > val) return;goal = root;if (root.right != null) search(root.right);
}

• 过程4：

xin麒之前所说对返回的goal进行处理是吧，其实没怎么简单就可以处理好，因为如果出现这个情况呢：

那么返回的goal其实是节点8，那么这样子不行呀，应该要返回在中序遍历的上一个节点4才对呀！

于是就需要有一个前节点来记录了：

最终结果：

class Solution {TreeNode goal = new TreeNode(Integer.MIN_VALUE);TreeNode before;int val;public TreeNode insertIntoBST(TreeNode root, int val) {if(root == null) return new TreeNode(val);this.val = val;search(root);if (goal.val > val){if (goal.left == null){goal.left = new TreeNode(val);}else {before.right = new TreeNode(val);}}else {goal.right = new TreeNode(val);}return root;}private void search(TreeNode root) {if (goal.val > val) return;if (root.left != null) search(root.left);if (goal.val > val) return;before = goal;goal = root;if (root.right != null) search(root.right);}
}

这里的before是记录旧数据的

怎么知道获取上面例子的节点值为8的是不对的，通过对goal来判断，判断如果左节点不为null不就可以了吗？左节点不为null说明该goal不是叶子节点。

end