●??235.?二叉搜索樹的最近公共祖先?
題目鏈接：https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/
在有序樹里面粮，如果判斷一個(gè)節(jié)點(diǎn)的左子樹里有p，右子樹里有q呢继低？
因?yàn)槭怯行驑浒静裕?如果 中間節(jié)點(diǎn)是 q 和 p 的公共祖先，那么 中節(jié)點(diǎn)的數(shù)組 一定是在 [p, q]區(qū)間的。即 中節(jié)點(diǎn) > p && 中節(jié)點(diǎn) < q 或者 中節(jié)點(diǎn) > q && 中節(jié)點(diǎn) < p
那么只要從上到下去遍歷柴底，遇到 cur節(jié)點(diǎn)是數(shù)值在[p, q]區(qū)間中則一定可以說明該節(jié)點(diǎn)cur就是q 和 p的公共祖先婿脸。并且cur就是 p和q的最近公共祖先
●??701.二叉搜索樹中的插入操作?
題目鏈接：https://leetcode.cn/problems/insert-into-a-binary-search-tree/
1. 確定遞歸函數(shù)參數(shù)以及返回值
參數(shù)就是根節(jié)點(diǎn)指針，以及要插入元素柄驻，這里遞歸函數(shù)要不要有返回值呢狐树？
可以有，也可以沒有凿歼，但遞歸函數(shù)如果沒有返回值的話褪迟，實(shí)現(xiàn)是比較麻煩的，下面也會給出其具體實(shí)現(xiàn)代碼答憔。有返回值的話，可以利用返回值完成新加入的節(jié)點(diǎn)與其父節(jié)點(diǎn)的賦值操作
2. 確定終止條件
終止條件就是找到遍歷的節(jié)點(diǎn)為null的時(shí)候掀抹，就是要插入節(jié)點(diǎn)的位置了虐拓，并把插入的節(jié)點(diǎn)返回。
3. 確定單層遞歸的邏輯
如何通過遞歸函數(shù)返回值完成了新加入節(jié)點(diǎn)的父子關(guān)系賦值操作了傲武，下一層將加入節(jié)點(diǎn)返回蓉驹，本層用root->left或者root->right將其接住
●??450.刪除二叉搜索樹中的節(jié)點(diǎn)?
題目鏈接：https://leetcode.cn/problems/delete-node-in-a-bst/submissions/
1. 確定遞歸函數(shù)參數(shù)以及返回值
說到遞歸函數(shù)的返回值，在二叉樹：搜索樹中的插入操作?(opens new window)中通過遞歸返回值來加入新節(jié)點(diǎn)揪利， 這里也可以通過遞歸返回值刪除節(jié)點(diǎn)态兴。
2. 確定終止條件
遇到空返回，其實(shí)這也說明沒找到刪除的節(jié)點(diǎn)疟位，遍歷到空節(jié)點(diǎn)直接返回了
3. 確定單層遞歸的邏輯
這里就把二叉搜索樹中刪除節(jié)點(diǎn)遇到的情況都搞清楚瞻润。
有以下五種情況：
第一種情況：沒找到刪除的節(jié)點(diǎn)，遍歷到空節(jié)點(diǎn)直接返回了
找到刪除的節(jié)點(diǎn)
第二種情況：左右孩子都為空（葉子節(jié)點(diǎn)）甜刻，直接刪除節(jié)點(diǎn)绍撞， 返回NULL為根節(jié)點(diǎn)
第三種情況：刪除節(jié)點(diǎn)的左孩子為空，右孩子不為空得院，刪除節(jié)點(diǎn)傻铣，右孩子補(bǔ)位，返回右孩子為根節(jié)點(diǎn)
第四種情況：刪除節(jié)點(diǎn)的右孩子為空祥绞，左孩子不為空非洲，刪除節(jié)點(diǎn)，左孩子補(bǔ)位蜕径，返回左孩子為根節(jié)點(diǎn)
第五種情況：左右孩子節(jié)點(diǎn)都不為空两踏，則將刪除節(jié)點(diǎn)的左子樹頭結(jié)點(diǎn)（左孩子）放到刪除節(jié)點(diǎn)的右子樹的最左面節(jié)點(diǎn)的左孩子上，返回刪除節(jié)點(diǎn)右孩子為新的根節(jié)點(diǎn)丧荐。
把新的節(jié)點(diǎn)返回給上一層缆瓣，上一層就要用 root->left 或者 root->right接住:
if (root->val > key) root->left = deleteNode(root->left, key);
if (root->val < key) root->right = deleteNode(root->right, key);
return root;
