二叉搜索树的插入，迭代版本以及递归版本

关于二叉搜索树的插入，这是非常常见的题目，关于二叉树的插入，在最开始的时候我想的很复杂，我想着这这个插入的节点可能在整个BST树的中间节点，也可能是根节点，也可能是叶子节点。情况非常复杂，最后发现针对这种题目，绝大多数的题解都是将这个节点插入到叶子节点处，当然这种插入方法就不太好，因为这种插入的方法可能导致整个BST的深度特别大。BST中文是二叉查找树，故名思意就是为了查找的，但是如果深度特别大，此时的查找效率和链表就差不多了，这种非常好的数据特性，我们就没利用到。为了保证BST 的查找树的查找效率，例如就有AVL树，通过查找节点以及二叉树的旋转操作，保证整个BST 树的深度，保证良好的搜索特性。

好了， 关于这道题目的一些背景说的差不多了，反正前期我最困惑的就是插入的节点应该放在哪里，这个问题。😢真滴是百思不得其解，直到我看了AVL树以及这道题目的题解。接下来的题解仍然是比较简单的叶子节点的插入，这里我书写一下关于递归以及迭代的版本

递归版本

递归的写法还是简洁明了的，过程如下：

• 如果 root 是空，则新建树节点作为根节点返回即可。
• 否则比较 root.val 与目标值的大小关系：
  如果 root.val 大于目标值，说明目标值应当插入 root 的左子树中，问题变为了在 root.left 中插入目标值，递归调用当前函数；
  如果 root.val 小于目标值，说明目标值应当插入 root 的右子树中，问题变为了在 root.right 中插入目标值，递归调用当前函数。

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val);
        }

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

迭代版本

• 如果 root 是空，则新建树节点作为根节点返回即可。
• 否则：
  1、初始化 cur 指向 root。
  2、比较 cur.val 与目标值的大小关系：
  • 如果 cur.val 大于目标值，说明目标值应当插入 cur 的左子树中，如果 cur.left 为 null，表明这是目标值可以插入的位置，直接插入并返回即可；否则 cur 指向 cur.left，重复步骤 2；
  • 如果 cur.val 小于目标值，说明目标值应当插入 cur 的右子树中。如果 cur.right 为 null，表明这是目标值可以插入的位置，直接插入并返回即可；否则 cur 指向 cur.right，重复步骤 2。

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        TreeNode node = new TreeNode(val);
        if (root == null) {
            return node;
        }

        TreeNode cur = root;
        while (true) {
            if (cur.val > val) {
                if (cur.left == null) {
                    cur.left = node;
                    break;
                }
                cur = cur.left;
            } else {
                if (cur.right == null) {
                    cur.right = node;
                    break;
                } 
                cur = cur.right;
            }
        }
        return root;
    }
}