问题

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

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

示例 1：
leetcode-701：二叉搜索树中的插入操作 - 图1
输入：root = [4,2,7,1,3], val = 5
输出：[4,2,7,1,3,5]
解释：另一个满足题目要求可以通过的树是：
leetcode-701：二叉搜索树中的插入操作 - 图2
示例 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]

思路

题目中的提示：有多种有效的插入方式，还可以重构二叉搜索树，瞬间感觉题目复杂了很多。

其实可以不考虑题目中提示所说的改变树的结构的插入方式

如下演示视频中可以看出：只要按照二叉搜索树的规则去遍历，遇到空节点就插入节点就可以了
leetcode-701：二叉搜索树中的插入操作 - 图3
例如插入元素10 ，需要找到末尾节点插入便可，一样的道理来插入元素15，插入元素0，插入元素6，「需要调整二叉树的结构么？并不需要。」

只要遍历二叉搜索树，找到空节点插入元素就可以了

解法一：递归

递归三部曲：

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

    • 参数就是根节点指针，以及要插入元素，这里递归函数要不要有返回值呢？
      • 可以有，也可以没有，但递归函数如果没有返回值的话，实现是比较麻烦的，下面也会给出其具体实现代码
      • 有返回值的话，可以利用返回值完成新加入的节点与其父节点的赋值操作
    • 递归函数的返回类型为节点类型TreeNode 
      1. TreeNode insertIntoBST(TreeNode root, int val)

  • 确定终止条件

    • 终止条件就是找到遍历的节点为null的时候，就是要插入节点的位置了，并把插入的节点返回
      1. if (root == null) {
      2. TreeNode node = new TreeNode(val);
      3. return node;
      4. }
      这里把添加的节点返回给上一层，就完成了父子节点的赋值操作了，详细再往下看

  • 确定单层递归的逻辑

    • 此时要明确，需要遍历整棵树么？ 别忘了这是搜索树，遍历整颗搜索树简直是对搜索树的侮辱， 搜索树是有方向了，可以根据插入元素的数值，决定递归方向
      1. if (root.val > val) 
      2. root.left = insertIntoBST(root.left, val);
      3. if (root.val < val) 
      4. root.right = insertIntoBST(root.right, val);
      5. return root;
      到这里，大家应该能感受到，如何通过递归函数返回值完成了新加入节点的父子关系赋值操作了，下一层将加入节点返回，本层用root.left或者root.right将其接住
      1. class Solution {
      2. public TreeNode insertIntoBST(TreeNode root, int val) {
      3.    if (root == null) {
      4.        TreeNode node = new TreeNode(val);
      5.        return node;
      6.    }
      7.    if (root.val > val) 
      8.        root.left = insertIntoBST(root.left, val);
      9.    if (root.val < val) 
      10.        root.right = insertIntoBST(root.right, val);
      11.    return root;
      12. }
      13. }


刚刚说了递归函数不用返回值也可以，找到插入的节点位置，直接让其父节点指向插入节点，结束递归，也是可以的

那么递归函数定义如下：

  1. TreeNode parent; // 记录遍历节点的父节点
  2. public void traversal(TreeNode cur, int val)

没有返回值，需要记录上一个节点（parent），遇到空节点了，就让parent左孩子或者右孩子指向新插入的节点，然后结束递归。

  1. class Solution {
  2.     TreeNode parent;
  3.     public void traversal(TreeNode cur, int val) {
  4.         if (cur == null) {
  5.             TreeNode node = new TreeNode(val);
  6.             if (val > parent.val) 
  7.                 parent.right = node;
  8.             else parent.left = node;
  9.             return;
  10.         }
  11.         parent = cur;
  12.         if (cur.val > val) 
  13.             traversal(cur.left, val);
  14.         if (cur.val < val) 
  15.             traversal(cur.right, val);
  16.         return;
  17.     }
  19.     public TreeNode insertIntoBST(TreeNode root, int val) {
  20.         parent = new TreeNode(0);
  21.         if (root == null) {
  22.             TreeNode root = new TreeNode(val);
  23.         }
  24.         traversal(root, val);
  25.         return root;
  26.     }
  27. }

解法二：迭代

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

  1. class Solution {
  2.     public TreeNode insertIntoBST(TreeNode root, int val) {
  3.         if (root == null) {
  4.             TreeNode node = new TreeNode(val);
  5.             return node;
  6.         }
  8.         TreeNode cur = root;
  9.         TreeNode parent = root; // 这个很重要，需要记录上一个节点，否则无法赋值新节点
  10.         while (cur != null) {
  11.             parent = cur;
  12.             if (cur.val > val) 
  13.                 cur = cur.left;
  14.             else cur = cur.right;
  15.         }
  17.         TreeNode node = new TreeNode(val);
  18.         if (val < parent.val) 
  19.             parent.left = node;// 此时是用parent节点进行赋值
  20.         else parent.right = node;
  21.         return root;
  22.     }
  23. }