- 235 二叉搜索樹的最近公共祖先
- 701 二叉搜索樹中的插入操作
- 450 刪除二叉搜索樹中的節(jié)點
235. 二叉搜索樹的最近公共祖先
給定一個二叉搜索樹, 找到該樹中兩個指定節(jié)點的最近公共祖先。
百度百科中最近公共祖先的定義為：“對于有根樹 T 的兩個結(jié)點 p梅肤、q楞陷，最近公共祖先表示為一個結(jié)點 x侠讯，滿足 x 是 p吆录、q 的祖先且 x 的深度盡可能大（一個節(jié)點也可以是它自己的祖先）柔吼≡砉桑”
方法一： 遞歸寫法
如果 cur->val 小于 p->val荷辕，同時 cur->val 小于 q->val途戒，那么就應(yīng)該向右遍歷（目標區(qū)間在右子樹）坑傅。反之，向左遍歷喷斋。
剩下的情況唁毒，就是cur節(jié)點在區(qū)間，那么cur就是最近公共祖先了继准，直接返回cur
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//遞歸三要素: 確定終止條件
if(root == null) return root;
//遞歸三要素： 單層邏輯
if(root.val > p.val && root.val > q.val){ //root值大于p,q枉证，向左尋找
return lowestCommonAncestor(root.left, p, q);
}else if(p.val > root.val && q.val > root.val){ //root值小于p,q，向右尋找
return lowestCommonAncestor(root.right, p, q);
}else{//root 位于p,q之間,root就是lowest Common Ancestor
return root;
}
}
}
方法二 . 迭代
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null) return root;
while(true){
if(root.val > p.val && root.val > q.val){
root = root.left;
}else if(root.val < p.val && root.val < q.val){
root = root.right;
}else{
break;
}
}
return root;
}
}
時間復(fù)雜度： O(n)
空間復(fù)雜度： O(1)
701. 二叉搜索樹中的插入操作
給定二叉搜索樹（BST）的根節(jié)點和要插入樹中的值移必，將值插入二叉搜索樹室谚。 返回插入后二叉搜索樹的根節(jié)點。 輸入數(shù)據(jù)保證，新值和原始二叉搜索樹中的任意節(jié)點值都不同秒赤。
思路： 只要按照二叉搜索樹的規(guī)則去遍歷猪瞬，遇到空節(jié)點就插入節(jié)點就可以了。
遞歸：
- 確定終止條件
終止條件就是找到遍歷的節(jié)點為null的時候入篮，就是要插入節(jié)點的位置了陈瘦，并把插入的節(jié)點返回。 - 確定單層遞歸的邏輯
根據(jù)BST特性潮售，如果root.val < val, 說明val應(yīng)該出現(xiàn)在root右側(cè)痊项，向右子樹尋找； 反之向左尋找
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;
}
}
迭代：
在迭代法遍歷的過程中酥诽，需要記錄一下當前遍歷的節(jié)點的父節(jié)點鞍泉，這樣才能做插入節(jié)點的操作
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
if(root == null) return new TreeNode(val);
TreeNode cur = root;
TreeNode pre = root; //當前遍歷的節(jié)點的父節(jié)點
while(cur != null){
pre = cur;
if(cur.val > val){
cur = cur.left;
}else{
cur = cur.right;
}
}
if(pre.val > val){
pre.left = new TreeNode(val);
}else{
pre.right = new TreeNode(val);
}
return root;
}
}
時間復(fù)雜度：O(N)，其中 N 為樹中節(jié)點的數(shù)目肮帐。最壞情況下咖驮，我們需要將值插入到樹的最深的葉子結(jié)點上，而葉子節(jié)點最深為 O(N)训枢。
空間復(fù)雜度：O(1)托修。我們只使用了常數(shù)大小的空間。
450. 刪除二叉搜索樹中的節(jié)點
給定一個二叉搜索樹的根節(jié)點 root 和一個值 key恒界，刪除二叉搜索樹中的 key 對應(yīng)的節(jié)點睦刃，并保證二叉搜索樹的性質(zhì)不變。返回二叉搜索樹（有可能被更新）的根節(jié)點的引用仗处。
一般來說眯勾，刪除節(jié)點可分為兩個步驟：
首先找到需要刪除的節(jié)點；
如果找到了婆誓，刪除它吃环。
刪除節(jié)點的五種情況：
- 樹中沒有需要刪除的節(jié)點
返回root - 要刪除的節(jié)點是葉子節(jié)點
直接刪除 - 要刪除的節(jié)點左空右不空
父節(jié)點直接指向右孩子 - 要刪除的節(jié)點右空左不空
父節(jié)點直接指向左孩子 - 要刪除的節(jié)點左右均不為空
左孩子繼位，原來的右子樹成為左孩子的最右葉子的右孩子
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
//沒有找到需要刪除的節(jié)點
if(root == null) return null;
if(key > root.val){
// 去右子樹刪除
root.right = deleteNode(root.right, key);
}else if(key < root.val){
// 去左子樹刪除
root.left = deleteNode(root.left, key);
}else{
//key found
//要刪除的節(jié)點是葉子節(jié)點
if (root.left == null && root.right == null) {
return null;
}
//要刪除的節(jié)點左空右不空, 父節(jié)點直接指向右孩子
if(root.left == null) return root.right;
//要刪除的節(jié)點右空左不空, 父節(jié)點直接指向左孩子
if(root.right == null) return root.left;
//左右都不為空洋幻，原來的右子樹成為左孩子的最右葉子的右孩子郁轻，左孩子繼位，
TreeNode cur = root.left;
while(cur.right != null){
cur = cur.right;
}
cur.right = root.right;
root = root.left; // 左孩子頂替被刪除節(jié)點的位置文留，節(jié)點被刪除
}
return root;
}
}
時間復(fù)雜度 O(n)
空間復(fù)雜度O(n)
