網(wǎng)站做統(tǒng)計(jì)愛站網(wǎng)挖掘工具
目錄
- 一、力扣235.二叉搜索樹的最近公共祖先
- 1.1 題目
- 1.2 思路
- 1.3 代碼
- 二、力扣701.二叉搜索樹中的插入操作
- 2.1 題目
- 2.2 思路
- 2.3 代碼
- 三、力扣450.刪除二叉搜索樹中的節(jié)點(diǎn)
- 3.1 題目
- 3.2 思路
- 3.3 代碼
- 3.4 總結(jié)
一、力扣235.二叉搜索樹的最近公共祖先
1.1 題目
1.2 思路
利用二叉搜索樹的有序特性來(lái)實(shí)現(xiàn):
如果cur大于pq:向左搜索;
如果cur小于pq:向右搜索;
如果介于兩者之間:則找到!
1.3 代碼
遞歸法:
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {//遞歸法if(root == null){return null;}return traversal(root,p,q);}public TreeNode traversal(TreeNode root,TreeNode p,TreeNode q){//和上題類似,第二種情況也包含在了處理邏輯里if(root.val < p.val && root.val < q.val){return traversal(root.right,p,q);}if(root.val > p.val && root.val > q.val){return traversal(root.left,p,q);}//當(dāng)前節(jié)點(diǎn)介于[p,q] 閉區(qū)間return root;}
}
迭代法:
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {//迭代if(root == null){return null;}TreeNode cur = root;while(true){if(cur.val > p.val && cur.val > q.val){cur = cur.left;continue;}if(cur.val < p.val && cur.val < q.val){cur = cur.right;continue;}return cur;}}
}
二、力扣701.二叉搜索樹中的插入操作
2.1 題目
2.2 思路
根據(jù)二叉搜索樹的特性,比大小向下遍歷,直到找到null,將其new一個(gè)新的結(jié)點(diǎn)插入進(jìn)去。
2.3 代碼
自己的思路:
class Solution {public TreeNode newnode;public TreeNode insertIntoBST(TreeNode root, int val) {//比大小來(lái)遍歷尋找該插入的位置if(root == null){return new TreeNode(val);}traversal(root,val);return root;}public void traversal(TreeNode root,int val){if(val > root.val){if(root.right == null){newnode = new TreeNode(val);root.right = newnode;return;}traversal(root.right,val);}if(val < root.val){if(root.left == null){newnode = new TreeNode(val);root.left = newnode;return;}traversal(root.left,val);}}
}
三、力扣450.刪除二叉搜索樹中的節(jié)點(diǎn)
3.1 題目
3.2 思路
梳理本題的五種情況:
(1)沒有找到該節(jié)點(diǎn)
(2)找到了該節(jié)點(diǎn),該節(jié)點(diǎn)的左右孩子均為空
(3)找到了該節(jié)點(diǎn),該節(jié)點(diǎn)的左孩子為空,右孩子不為空
(4)找到了該節(jié)點(diǎn),該節(jié)點(diǎn)的左孩子不為空,右孩子為空
(5)找到了該節(jié)點(diǎn),該節(jié)點(diǎn)的左右孩子均不為空(最關(guān)機(jī)鍵的點(diǎn)):見下圖
3.3 代碼
class Solution {public TreeNode deleteNode(TreeNode root, int key) {//確定遞歸的終止條件//沒有找到該節(jié)點(diǎn)if(root == null){return null;}//找到了該節(jié)點(diǎn)if(root.val == key){if(root.left == null && root.right == null){return null;}else if(root.left != null && root.right == null){return root.left;}else if(root.left == null && root.right != null){return root.right;}else{//假設(shè)root的右子樹上位,那么需要將root的左子樹插入root的右子樹中,再返回右子樹TreeNode cur = root.right;while(cur.left != null){cur = cur.left;}cur.left = root.left;return root.right;}}//單層遞歸邏輯if(key > root.val){root.right = deleteNode(root.right,key);}if(key < root.val){root.left = deleteNode(root.left,key);}return root;}
}
3.4 總結(jié)
(1)五種情況的分析;(遞歸終止條件)
(2)不用雙指針pre,而是將處理后的結(jié)點(diǎn)回溯返回給上層節(jié)點(diǎn)接住。(單層遞歸邏輯)