701. Insert into a Binary Search Tree

題目：
給你一棵二元搜尋樹和一個整數 val，請將 val 插入 BST 中，並回傳插入後的根節點

範例：

• Example 1:
  Input: root = [4,2,7,1,3], val = 5
  Output: [4,2,7,1,3,5]
  Explanation: Another accepted tree is:

• Example 2:
  Input: root = [40,20,60,10,30,50,70], val = 25
  Output: [40,20,60,10,30,50,70,null,null,25]

• Example 3:
  Input: root = [4,2,7,1,3,null,null,null,null,null,null], val = 5
  Output: [4,2,7,1,3,5]

想法：
目標：將val值放進二元搜尋數中（符合左小右大）

1. 將val與節點比較
   -val < 節點 ——＞右子數
   -val >= 節點 ——＞左子樹
2. By遞迴

程式碼：

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if(root == null)return new TreeNode(val);
        if(val < root.val){ //val小於目前節點的值，插入到左子樹
            root.left = insertIntoBST(root.left, val);
        }else{              //val大於或等於目前節點的值，插入到右子樹
            root.right = insertIntoBST(root.right, val);
        }
        return root;
    }
}

實際操作：

要插入 val = 5

root = 4
val = 5

STEP1
5 > 4 → 走到右子樹
root.right = insertIntoBST(root.right, 5);
——＞root = 4
——＞root.right = 7

STEP2
遞迴到 node = 7
val (5) < 7 → 走到左子樹
root.left = insertIntoBST(root.left, 5);
——＞root = 7
——＞root.left = null

STEP3
遞迴到 node = null
root == null → 建立新節點
return new TreeNode(5)

STEP4
遞迴回到 node = 7
root.left = new TreeNode(5)
——＞樹變成：

STEP5
遞迴回到 node = 4
root.right = (更新後的 7)
——＞樹變成：

——＞插入後 BST:
[4, 2, 7, null, null, 5]