文章目錄
- 二叉樹的最近公共祖先
- 二叉搜索樹的最近公共祖先
- 二叉搜索樹中的插入操作
- 刪除二叉搜索樹中的節點
二叉樹的最近公共祖先
題目鏈接:236. 二叉樹的最近公共祖先
解題邏輯:
最近公共祖先的定義為:對于有根樹 T 的兩個節點 p、q,最近公共祖先表示為一個節點 x,滿足 x 是 p、q 的祖先且 x 的深度盡可能大(一個節點也可以是它自己的祖先)
我們想要尋找兩個節點的最近公共祖先,是一個從下向上尋找的過程,那么我們可以通過遞歸中的歸來解決(向下遞,向上歸)。
我們可以通過兩種思路來解決這個問題:
- 遞歸的返回值的傳遞
- 回溯算法
這兩種思路都可以實現從下到上的邏輯處理。
這里我們使用遞歸返回值這種方法。
從遞歸三要素來考慮,本題采用后序遍歷:
- 遞歸參數與返回值:遞歸的參數就是根節點、以及兩個樹節點。而遞歸的返回值是可以層層向上傳遞的,我們可以設置為set,代表當前節點的左右子樹中包含p、q中的哪個節點。
- 遞歸的出口:當node為null的時候,返回空set即可
- 遞歸邏輯:
- 獲得左、右節點所具有的孩子節點
- 創建一個新set
- 如果當前節點是p、q中的一個則將當前節點放入set
- 將當前set與左右節點返回的set合并
- 如果合并之后set中同時包含p、q則說明該節點為最近的公共祖先,將其賦值給類字段
- 否則返回set
代碼如下:
class Solution {TreeNode result = null;boolean first = true;public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {findTree(root,p.val,q.val);return result;}public Set<Integer> findTree(TreeNode node,Integer p,Integer q){if(node == null) return new HashSet<Integer>();Set<Integer> left = findTree(node.left,p,q);Set<Integer> right = findTree(node.right,p,q);Set<Integer> set = new HashSet<>();if(node.val == p) set.add(p);else if(node.val == q) set.add(q);set.addAll(left);set.addAll(right);if(set.contains(p) && set.contains(q) && first) {result = node;first = false;}return set;}
}
上面這種算法的核心邏輯就是:只要該節點的左右子樹中包含p、q中的任意一個就向上傳遞,當某一節點湊齊p、q那么就說明該節點是p、q最近的公共祖先。
當然上面的算法效率并不高,我們可以根據題意簡潔一下算法,將遞歸的返回值換為boolean,只要子樹中包含p或者q就返回true,代碼如下:
class Solution {TreeNode result = null;public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {findTree(root,p.val,q.val);return result;}public boolean findTree(TreeNode node,Integer p,Integer q){if(node == null) return false;boolean left = findTree(node.left,p,q);boolean right = findTree(node.right,p,q);if(left && right) {result = node;return true;}else if(node.val == p && (left || right)) {result = node;return true;}else if(node.val == q && (left || right)){result = node;return true;}else if(node.val == q || node.val == p) {return true;}return left || right;}
}
二叉搜索樹的最近公共祖先
題目鏈接:235. 二叉搜索樹的最近公共祖先
解題邏輯:
這個題可以直接使用上面的代碼,但是效率很低,因為沒有使用到二叉搜索樹的特性。
在二叉搜索樹中要想找到兩個節點p、q的最近公共祖先,我們可以從上往下遍歷。
- 如果當前節點數值小于p、q兩個節點,那么說明p、q均在該節點的右子樹中,繼續往右子樹中搜索
- 如果當前節點數值大于p、q兩個節點,那么說明p、q均在該節點的左子樹中,繼續往左子樹中搜索
- 如果當前節點的數值在p、q兩個節點之間,那么就說明該節點就為p、q的最近公共節點(此時p、q肯定分別在該節點的左右子樹上,不會有更近的,因為如果繼續深入尋找,進入任意一邊的子樹都將失去另一邊子樹的節點)
代碼如下:
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root == null) return null;TreeNode left = null;TreeNode right = null;if(root.val > Math.max(p.val,q.val)) left = lowestCommonAncestor(root.left,p,q);else if(root.val < Math.min(p.val,q.val)) right = lowestCommonAncestor(root.right,p,q);else if(root.val >= Math.min(p.val,q.val) && root.val <= Math.max(p.val,q.val)) return root;if(left != null) return left;else if(right != null) return right;return null;}
}
二叉搜索樹中的插入操作
題目鏈接:701. 二叉搜索樹中的插入操作
解題邏輯:
若二叉搜索樹為空,則直接插入節點。否則若val小于跟節點值,則插入到左子樹。相反則插入到右子樹。
代碼如下:
class Solution {public TreeNode insertIntoBST(TreeNode root, int val) {if(root == null) return new TreeNode(val);if(val < root.val) {TreeNode left = insertIntoBST(root.left,val);root.left = left;}else {TreeNode right = insertIntoBST(root.right,val);root.right = right;}return root;}
}
刪除二叉搜索樹中的節點
題目鏈接: 450. 刪除二叉搜索樹中的節點
刪除二叉樹中的節點分為三種情況:
- 若被刪除節點是葉子節點,則直接刪除
- 若被刪除節點只有一棵子樹,則直接讓其子樹替代位置即可
- 若被刪除節點有兩顆子樹,則讓被刪除節點的直接后繼(或者直接前驅)替代被刪除節點,然后從二叉搜索樹中刪除這個直接后繼(或者直接前驅),這樣就轉換成了前面兩種情況
代碼如下:
class Solution {int preNum = Integer.MAX_VALUE;public TreeNode deleteNode(TreeNode root, int key) {if(root == null) return null;TreeNode left = deleteNode(root.left,key);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 if(root.left != null && root.right != null) {int rem = preNum;TreeNode node = deleteNode(root,rem);node.val = rem;preNum = rem;return node;}}preNum = root.val;TreeNode right = deleteNode(root.right,key);root.left = left;root.right = right;return root;}
}