1.插入

題目描述：
給定二叉搜索樹（BST）的根節點和要插入樹中的值，將值插入二叉搜索樹， 回傳插入后二叉搜索樹的根節點， 輸入資料 保證 ，新值和原始二叉搜索樹中的任意節點值都不同，

注意，可能存在多種有效的插入方式，只要樹在插入后仍保持為二叉搜索樹即可， 你可以回傳 任意有效的結果 ，

鏈接：https://leetcode-cn.com/problems/insert-into-a-binary-search-tree

思路分析：該樹就為一顆二叉搜索樹（bst），左邊的比根節點都小，右邊的比根節點都大，

插入的時候，該節點一定會新開辟一個節點，并插入在根節點的左邊或者右邊，

1. 大于根節點，插入在右邊，
2. 小于根節點，插入在左邊，

比如插入35：

比如插入18：

1.1 遞回

代碼：

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if(root == nullptr)//為空，此時就可以插入了
        {
            TreeNode * p = new TreeNode(val);
            return p;
        }
        if(root->val > val)  //當前根節點值大于val則在左邊插入
            root->left = insertIntoBST(root->left, val);
        if(root->val < val)//在右邊插入
            root->right = insertIntoBST(root->right, val);
        return root;//插入之后，直接回傳
    }
};

1.2 迭代

代碼：

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if(root == nullptr)
            return new TreeNode(val);
        TreeNode* p = root;
        while(p != nullptr)
        {
            if(p->val > val)//根節點值大，左邊插入
            {
                if(p->left == nullptr)//p的左側為空，可以插入了，因為小于根節點，則在左側插入
                {
                    p->left = new TreeNode(val);
                    break;
                }
                p = p->left;//還不能插入，改變當前節點位置
            }
            else//根節點值小，右邊插入
            {
                if(p->right == nullptr)//p的右側為空，可以插入了，因為大于根節點，則在右側插入
                {
                    p->right = new TreeNode(val);
                    break;
                }
                p = p->right;//還不能插入，改變當前節點位置
            }
        }
        return root;//回傳
    }
};

2. 洗掉

給定一個二叉搜索樹的根節點 root 和一個值 key，洗掉二叉搜索樹中的 key 對應的節點，并保證二叉搜索樹的性質不變，回傳二叉搜索樹（有可能被更新）的根節點的參考，

一般來說，洗掉節點可分為兩個步驟：

首先找到需要洗掉的節點；
如果找到了，洗掉它，
說明： 要求演算法時間復雜度為 O(h)，h 為樹的高度，

鏈接：https://leetcode-cn.com/problems/delete-node-in-a-bst

bst的洗掉，不能直接釋放該節點，否則該樹就崩潰了，

1. 第一種情況：在左邊尋找最大值然后洗掉，兩者值交換，然后洗掉
   
   這樣該樹，仍然是一顆二叉搜索樹

2. 第二種情況：在右邊尋找最小值然后洗掉，兩者值交換
   這樣該樹，仍然是一顆二叉搜索樹，

注意的點：

1. 要洗掉的節點，左右都不為空時，則分兩種情況，洗掉左邊最大值還是右邊最小值
2. 若有一邊為空了，則可以進行洗掉了，當前節點洗掉，回傳其另一邊的節點

代碼：

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if(root == nullptr)//當前為空，直接回傳
            return nullptr;
        if(root->val > key)//大于該值，該值在左邊，向左邊找
            root->left = deleteNode(root->left, key);
        else if(root->val < key)//小于該值，該值在右邊，向右邊找
            root->right = deleteNode(root->right, key);
        else//找到了
        {
            if(root->left != nullptr && root->right != nullptr)//左右子樹皆不為空
            {
                TreeNode* s = root->right;//第二種情況，去找右邊最小的值
                while(s->left != nullptr)
                    s = s->left;
                root->val = s->val;//此時就找到了，右邊最小的值，改變當前值
                root->right = deleteNode(root->right, root->val);//右邊去洗掉右邊的最小值
            }
            else//可以洗掉了
            {
                if(root->left != nullptr)//左不為空
                {
                    TreeNode* s = root;//
                    root = root->left;//改變當前位置
                    delete s;//釋放節點，leetcode沒要求洗掉，但為了寫代碼的習慣，建議洗掉
                }
                else//右可能為空，可能不為空，不重要，為慷訓傳空即可
                {
                    TreeNode* s = root;
                    root = root->right;//改變當前位置
                    delete s;//釋放節點，leetcode沒要求洗掉，但為了寫代碼的習慣，建議洗掉
                }
            }
        }
        return root;//回傳
    }
};

//第一種情況也給出
            if(root->left != nullptr && root->right != nullptr)
            {
                TreeNode* s = root->left;//去找左邊最大值
                while(s->right != nullptr)
                    s = s->right;
                root->val = s->val;//找到了，改變值
                root->left = deleteNode(root->left, root->val);//左邊去洗掉左邊最大值
            }