非递归方式
    这题说的是让在二叉搜索树中插入一个节点，最简单的一种方式就是插入到叶子节点。 二叉搜索树的特点是左子树的值都小于当前节点，右子树的值都大于当前节点，并且左 右子树都具有这个特性。所以我们需要用插入的值val和根节点比较，
    如果val大于根节点，说明值为val的节点应该插入到root节点的右子树上
    如果val小于根节点，说明值为val的节点应该插入到root节点的左子树上
    image.png
    image.png

    1. public TreeNode insertIntoBST(TreeNode root, int val) {
    2.     // 如果是空树，直接构造根节点
    3.     if (root == null) return new TreeNode(val);
    5.     TreeNode cur = root;
    6.     while (true) {
    7.         // 如果当前节点cur的值大于val，说明val值应该插入到
    8.         // 当前节点cur的左子树，否则就插入到当前节点cur的右子树
    9.         if (cur.val > val) {
    10.             if (cur.left != null) {
    11.                 cur = cur.left;
    12.             } else {
    13.                 // 如果左子节点为空，就直接插入去，然后再返回root节点
    14.                 cur.left = new TreeNode(val);
    15.                 return root;
    16.             }
    17.         } else {
    18.             // 同上
    19.             if (cur.right != null) {
    20.                 cur = cur.right;
    21.             } else {
    22.                 cur.right = new TreeNode(val);
    23.                 return root;
    24.             }
    25.         }
    26.     }
    27. }

    递归方式解决
    递归的方式原理还和上面一样，一直往下找，直到找到叶子节点为止，代码如下

    1. public TreeNode insertIntoBST(TreeNode root, int val) {
    2.     // 边界条件判断，只剩下一个节点直接添加
    3.     if (root == null) return new TreeNode(val);
    5.     // 如果root节点的值大于val，说明值为val的节点应该在root节点的左子树上
    6.     if (root.val > val) root.left = insertIntoBST(root.left, val);
    7.     if (root.val < val) root.right = insertIntoBST(root.right, val);
    9.     return root;
    10. }