235. 二叉搜索樹(shù)的最近公共祖先
題目鏈接/文章講解
相對(duì)于 二叉樹(shù)的最近公共祖先 本題就簡(jiǎn)單一些了爬范，因?yàn)?可以利用二叉搜索樹(shù)的特性。
思路
- 利用二叉搜索樹(shù)的特性來(lái)找
- 如果遍歷根節(jié)點(diǎn)弱匪，如果根節(jié)點(diǎn)大于p,q青瀑，說(shuō)明公共節(jié)點(diǎn)一定在左子樹(shù)；
- 如果根節(jié)點(diǎn)小于p和q萧诫，說(shuō)明公共節(jié)點(diǎn)一定在右子樹(shù)斥难；
- 如果在p和q之間，說(shuō)明就是公共祖先（但一定是最近的公共祖先嗎帘饶？如果公共祖先節(jié)點(diǎn)在p和q之間哑诊，那么p一定在左子樹(shù)，q一定在右子樹(shù)及刻。如果繼續(xù)向左遍歷镀裤，將錯(cuò)過(guò)p；繼續(xù)向右遍歷缴饭，將錯(cuò)過(guò)q暑劝，所以這一定是最近公共祖先）。
- 本題的迭代法代碼也很簡(jiǎn)單
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//遞歸
if(root == null) return null;
//這道題不需要涉及前中后序颗搂，因?yàn)闆](méi)有處理中間節(jié)點(diǎn)
//大于p担猛，q，往左子樹(shù)搜索
if(root.val > p.val && root.val > q.val){
TreeNode left = lowestCommonAncestor(root.left, p, q);
if(left != null){
return left;
}
}
if(root.val < p.val && root.val < q.val){
TreeNode right = lowestCommonAncestor(root.right, p, q);
if(right != null){
return right;
}
}
return root;
}
}
簡(jiǎn)潔寫(xiě)法
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//遞歸
if(root == null) return null;
//這道題不需要涉及前中后序丢氢，因?yàn)闆](méi)有處理中間節(jié)點(diǎn)
//大于p傅联，q，往左子樹(shù)搜索
if(root.val > p.val && root.val > q.val) return lowestCommonAncestor(root.left, p, q);
if(root.val < p.val && root.val < q.val) return lowestCommonAncestor(root.right, p, q);
return root;
}
}
迭代法的代碼
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
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;
}
}
701.二叉搜索樹(shù)中的插入操作
題目鏈接/文章講解
本題比想象中的簡(jiǎn)單疚察，大家可以先自己想一想應(yīng)該怎么做蒸走，然后看視頻講解，就發(fā)現(xiàn) 本題為什么比較簡(jiǎn)單了貌嫡。
思路
- 有多種有效的插入方式比驻，還可以重構(gòu)二叉搜索樹(shù)
- 二叉搜索樹(shù)插入的值都可以在葉子節(jié)點(diǎn)找到插入位置，保證有序性即可
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
//終止條件
if(root == null) return new TreeNode(val); // 如果當(dāng)前節(jié)點(diǎn)為空衅枫，也就意味著val找到了合適的位置嫁艇，此時(shí)創(chuàng)建節(jié)點(diǎn)向上一層返回
//向左遍歷
if(val < root.val){
root.left = insertIntoBST(root.left, val); //讓原來(lái)的節(jié)點(diǎn)和插入的節(jié)點(diǎn)連接起來(lái)
//向右遍歷
}else if(val > root.val){
root.right = insertIntoBST(root.right, val);
}
return root;
}
}
450.刪除二叉搜索樹(shù)中的節(jié)點(diǎn)
題目鏈接/文章講解
相對(duì)于 插入操作，本題就有難度了弦撩，涉及到改樹(shù)的結(jié)構(gòu)
思路
- 第一種情況：沒(méi)找到刪除的節(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)的左子樹(shù)頭結(jié)點(diǎn)（左孩子）放到刪除節(jié)點(diǎn)的右子樹(shù)的最左面節(jié)點(diǎn)的左孩子上闰挡，返回刪除節(jié)點(diǎn)右孩子為新的根節(jié)點(diǎn)锐墙。
偽代碼思路
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) return root; // 第一種情況：沒(méi)找到刪除的節(jié)點(diǎn)，遍歷到空節(jié)點(diǎn)直接返回长酗，返回值是在下面的遞歸中接住的
if (root.val == key) {
// 第二種情況：左右孩子都為空（葉子節(jié)點(diǎn)）溪北，直接刪除節(jié)點(diǎn)， 返回null為根節(jié)點(diǎn)
if (root.left == null && root.right == null) {
return null;
}
// 第三種情況：其左孩子為空夺脾，右孩子不為空之拨，刪除節(jié)點(diǎn)，右孩子補(bǔ)位 咧叭，返回右孩子為根節(jié)點(diǎn)
else if (root.left == null) {
return root.right;
}
// 第四種情況：其右孩子為空蚀乔，左孩子不為空，刪除節(jié)點(diǎn)佳簸，左孩子補(bǔ)位乙墙，返回左孩子為根節(jié)點(diǎn)
else if (root.right == null) {
return root.left;
}
// 第五種情況：左右孩子節(jié)點(diǎn)都不為空，將刪除節(jié)點(diǎn)的左子樹(shù)放到刪除節(jié)點(diǎn)的右子樹(shù)的最左面節(jié)點(diǎn)的左孩子的位置
// 并返回刪除節(jié)點(diǎn)右孩子為新的根節(jié)點(diǎn)生均。
else {
TreeNode cur = root.right; // 找右子樹(shù)最左面的節(jié)點(diǎn)
while (cur.left != null) {
cur = cur.left;
}
cur.left = root.left; // 把要?jiǎng)h除的節(jié)點(diǎn)（root）左子樹(shù)放在cur的左孩子的位置
root = root.right; // 返回舊root的右孩子作為新root
return root;
}
}
if (root.val > key) root.left = deleteNode(root.left, key);
if (root.val < key) root.right = deleteNode(root.right, key);
return root;
}
沒(méi)有看普通二叉樹(shù)的刪除方式，二刷再看
