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]

【思路】

递归

递归三部曲：

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

  TreeNode insertIntoBST(TreeNode root, int val);
  

• 确定终止条件

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

  if (root == null) 
  	return new TreeNode(val);
  

• 确定单层递归的逻辑

  if (root.val > val) {
  	root.left = insertInToBST(root.left, val);
  }
  if (root.val < val) {
  	root.right = insertIntoBST(root.right, val);
  }
  return root;
  

  总结

  首先在二叉搜索树中的插入操作，大家不用恐惧其重构搜索树，其实根本不用重构。

  然后在递归中，我们重点讲了如何通过递归函数的返回值完成新加入节点和其父节点的赋值操作，并强调了搜索树的有序性。

  最后依然给出了迭代的方法，迭代的方法就需要记录当前遍历节点的父节点了，这个和没有返回值的递归函数实现的代码逻辑是一样的。

  class Solution {
      public TreeNode insertIntoBST(TreeNode root, int val) {
          if (root == null) return new TreeNode(val);
          TreeNode newRoot = root;
          TreeNode pre = root;
          while (root != null) {
              pre = root;
              if (root.val > val) {
                  root = root.left;
              } else if (root.val < val) {
                  root = root.right;
              } 
          }
          if (pre.val > val) {
              pre.left = new TreeNode(val);
          } else {
              pre.right = new TreeNode(val);
          }
  
          return newRoot;
      }
  }
  

  递归法

  class Solution {
      public TreeNode insertIntoBST(TreeNode root, int val) {
          if (root == null) // 如果当前节点为空，也就意味着val找到了合适的位置，此时创建节点直接返回。
              return new TreeNode(val);
              
          if (root.val < val){
              root.right = insertIntoBST(root.right, val); // 递归创建右子树
          }else if (root.val > val){
              root.left = insertIntoBST(root.left, val); // 递归创建左子树
          }
          return root;
      }
  }