本周的力扣周結我并沒有刷很多的題，回溯模塊最近才開始刷，先把樹鞏固好
700. 二叉搜索樹中的搜索
解題思路
利用二叉搜索樹的性質去尋找指定值的結點（假設樹中結點沒有重復元素），二叉搜索樹中根節點的左孩子一定小于其根節點，根節點的右孩子一定大于其根節點，因為我們需要回傳指定的子樹所以，我們遞回函式的回傳值不為空
核心代碼
class Solution {
public TreeNode searchBST(TreeNode root, int val) {
//遞回結束的標志是找到了符合題目要求的根節點或是遍歷到了空結點
if(root == null || root.val == val){
return root;
}
TreeNode node = null;
if(root.val > val){
node = searchBST(root.left, val);
}
if(root.val < val){
node = searchBST(root.right, val);
}
return node;
}
}
時間復雜度
O(n)
空間復雜度
O(n)
98. 驗證二叉搜索樹
解題思路
中序遍歷二叉搜索樹，要遍歷每一個結點判斷每一個結點都是否符合二叉搜索樹的性質，
核心代碼
class Solution {
//進階：不使用額為的空間
TreeNode max;
public boolean isValidBST(TreeNode root) {
//遍歷到葉子節點
if(root == null) {
return true;
}
//左
if(!isValidBST(root.left)) {
return false;
}
//中
if(max != null && root.val <= max.val) {
return false;
}
max = root;
//右
return isValidBST(root.right);
}
}
時間復雜度
O(n)
空間復雜度
O(n)
530. 二叉搜索樹的最小絕對差
解題思路
這道題和上一題的思路大概一致，要中序遍歷每個二叉搜索樹的結點，并且要記錄父結點，用于上一層的呼叫
核心代碼
class Solution {
TreeNode node;
int min = Integer.MAX_VALUE;
public int getMinimumDifference(TreeNode root) {
inorder(root);
return min;
}
public void inorder(TreeNode root) {
//遍歷到葉子結點
if(root == null) {
return;
}
inorder(root.left);
if(node != null && root.val - node.val < min) {
min = root.val - node.val;
}
node = root;
inorder(root.right);
}
}
時間復雜度
O(n)
空間復雜度
O(n)
501. 二叉搜索樹中的眾數
解題思路
這道題力扣雖然表為easy是因為可以使用暴力破解，如果使用純遞回的的話，還是比較難的，還是利用二叉搜索樹的性質，中序遍歷相當于從小到大遍歷，使用一個ThreeNode型別來記錄前驅結點，使用一個額外的空間來記錄出現的次數，如果當前結點和前驅結點不等就重新記錄
核心代碼
class Solution {
//記錄出現的最大值次數
int max = 1;
//記錄前驅元素的出現次數
int temp = 1;
//記錄前驅元素
TreeNode node;
//定義結果集
ArrayList<Integer> mode = new ArrayList<>();
public int[] findMode(TreeNode root) {
inorder(root);
int[] result = new int[mode.size()];
for(int i = 0; i < result.length; i++) {
result[i] = mode.get(i);
}
return result;
}
//相當于是求遞增序列的眾數
public void inorder(TreeNode root) {
if(root == null) {
return;
}
inorder(root.left);
//當前結點的前一個結點如果不等就直接讓temp = 1
if(node == null || root.val != node.val) {
temp = 1;
} else {
temp++;
}
if(temp > max) {
mode.clear();
mode.add(root.val);
max = temp;
} else if (temp == max) {
mode.add(root.val);
}
node = root;
inorder(root.right);
}
}
時間復雜度
O(n)
空間復雜度
O(n)
236. 二叉樹的最近公共祖先
解題思路
尋找最近的公共祖先，如果發現一個結點，它的左子樹和右子樹分別包括左右結點那么就找到了公共祖先，所以我們可以后序遍歷二叉樹
核心代碼
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//遞回結束的條件遍歷到目標結點或是空結點
if(root == p || root == q || root == null) {
return root;
}
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
//如果左右結點不為空就證明找到了結點，回傳當前結點
if(left != null && right != null) {
return root;
}
//如果左子樹為空直接回傳右子樹即可
//右子樹有兩種情況：1.為空 2.不為空
if(left == null) {
return right;
}
//左子樹不為空，右子樹為空
return left;
}
}
時間復雜度
O(n)
空間復雜度
O(n)
235. 二叉搜索樹的最近公共祖先
解題思路
區別于上一道題，這道題的搜索可以依賴于二叉樹的性質，如果要尋找的結點的值都大于根結點那么就尋找他的右子樹，如果尋找的結點的值都小于根節點那么就尋找左子樹，如果都不是就證明尋找的值分布在跟結點的兩側，直接回傳根節點即可，
核心代碼
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//如果兩個結點的值比父結點大，那么一定在右側
if(p.val > root.val && q.val > root.val) {
return lowestCommonAncestor(root.right, p, q);
} else if (p.val < root.val && q.val < root.val) {
return lowestCommonAncestor(root.left, p, q);
}
return root;
}
}
時間復雜度
O(n)
空間復雜度
O(n)
701. 二叉搜索樹中的插入操作
解題思路
二叉搜索樹的插入是不需要破壞原有樹的結構的，所以我們直接利用二叉搜索樹的性質即可完成插入
核心代碼
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
//如果結點為空那么就回傳空結點
if(root == null) {
root = new TreeNode(val);
return root;
}
//如果父結點的值比val大那就一定插入在左子樹
if(root.val > val) {
root.left = insertIntoBST(root.left, val);
} else if (root.val < val) { //如果父結點的值比val小那就一定插入在右子樹
root.right = insertIntoBST(root.right, val);
}
return root;
}
}
時間復雜度
O(n)
空間復雜度
O(n)
450. 洗掉二叉搜索樹中的節點
解題思路
洗掉二叉樹的結點，情況涉及的就比較多了，這五種情況必須全部考慮到
- 如果洗掉的是葉子結點，那么直接洗掉就好了
- 如果洗掉的結點右孩子不為空，那么洗掉結點回傳右孩子就好了
- 如果洗掉的結點左孩子不為空但是右孩子為空，那么直接洗掉結點回傳左孩子就好了
- 如果洗掉的結點左右孩子都不為空，那么就將左孩子的根節點連接到，右孩子最左子樹的根節點上
- 如果就找不到洗掉結點，直接回傳根節點即可
這道題不需要遍歷所有的結點，只需要洗掉待洗掉的結點回傳最終結果即可
核心代碼
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
//1.找不到該結點遍歷到葉子結點直接回傳
if(root == null) {
return root;
}
//如果找到這個結點
if(root.val == key) {
//2.如果結點的左右孩子都為空，那么直接洗掉該結點即可
if(root.left == null && root.right == null) {
return null;
//3.如果結點的左孩子不為空，右孩子為空那么就將右孩子移上去
}else if (root.left != null && root.right == null) {
root = root.left;
return root;
//4.如果結點的右孩子不為空，左孩子為空那么就將左孩子移上去
}else if (root.left == null && root.right != null) {
root = root.right;
return root;
//5.如果結點左右孩子都不為空，那么就將左孩子的跟結點移動到有孩子的根節點的最左根節點的左孩子，然后右孩子移動到根節點
}else if (root.left != null && root.right != null) {
TreeNode temp = root.right;
while(temp.left != null) {
temp = temp.left;
}
temp.left = root.left;
root = root.right;
return root;
}
}
if(key < root.val) {
root.left = deleteNode(root.left, key);
}else {
root.right = deleteNode(root.right, key);
}
return root;
}
}
時間復雜度
O(n)
空間復雜度
O(n)
669. 修剪二叉搜索樹
解題思路
這道題和450基本類似，好多題都能看到卡哥的用心良苦，這套力扣刷題攻略我已經走了大半學到了很多東西，從剛開始的恐懼演算法到現在每天不刷兩三個小時渾身不自在，感謝卡哥
核心代碼
class Solution {
public TreeNode trimBST(TreeNode root, int low, int high) {
//1.如果結點為空
if(root == null) {
return root;
}
//左
root.left = trimBST(root.left, low, high);
//右
root.right = trimBST(root.right, low, high);
//中 找到不在范圍內的根節點
if(root.val < low || root.val > high) {
//2.根節點的左右孩子都為空直接洗掉該結點即可
if(root.left == null && root.right == null) {
root = null;
return root;
//3.左孩子不為空右孩子為空
}else if (root.left != null && root.right == null) {
root = root.left;
return root;
//4.右孩子不為空左孩子為空
}else if (root.left == null && root.right != null) {
root = root.right;
return root;
//5.左右孩子都不為空
}else {
TreeNode temp = root.right;
while(temp.left != null) {
temp = temp.left;
}
temp.left = root.left;
root = root.right;
return root;
}
}
return root;
}
}
時間復雜度
O(n)
空間復雜度
O(n)
108. 將有序陣列轉換為二叉搜索樹
解題思路
注意越界條件
核心代碼
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return build(nums, 0, nums.length - 1);
}
//區間的定義，左閉右閉
public TreeNode build(int[] nums, int left, int right) {
if (left > right) {
return null;
}
int mid = left + (right - left) / 2;
TreeNode root = new TreeNode(nums[mid]);
root.left = build(nums, left, mid - 1);
root.right = build(nums, mid + 1, right);
return root;
}
}
時間復雜度
O(n)
空間復雜度
O(logn)
538. 把二叉搜索樹轉換為累加樹
解題思路
這道題的難點應該是在于對題目的理解吧
核心代碼
class Solution {
int sum = 0;
public TreeNode convertBST(TreeNode root) {
if(root == null) {
return null;
}
convertBST(root.right);
sum += root.val;
root.val = sum;
convertBST(root.left);
return root;
}
}
時間復雜度
O(n)
空間復雜度
O(n)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/374769.html
標籤：其他
下一篇：華為防火墻配置（防火墻NAT）