摘要:題目意思就是要一個個的返回當前的最小值。所以解法自然就是。我們需要找出被打亂的點并返回正確結果。然后將兩個不正確的點記錄下來,最后回原來正確的值。如果是葉子節點,或者只有一個子樹。思想來自于的代碼實現。
跳過總結請點這里:
https://segmentfault.com/a/11...
BST最明顯的特點就是root.left.val < root.val < root.right.val.
還有另一個特點就是,bst inorder traversal result is an ascending array.
下面簡單表示一個BST:
60 / 40 80 / / 20 50 70 90 / 10 30 100
BST inorder traversal result is: 10 20 30 40 50 60 70 80 90 100.
BST 和普通的樹的區別就在于它是一個有序的,為了保證順序,我們需要通過inorder traversal得到,所以幾乎所有leetcode關于bst的題目,都是在考我們如何利用inorder traverse.
簡單題目只過代碼思路,代碼會附在題號底下,為了減少博客篇幅,題目描述細節請參看leetcode。
LC 173 Binary Search Tree Iterator.
Calling next() will return the next smallest number in the BST.
題目意思就是要一個個的返回bst當前的最小值。強提示:有序。
所以解法自然就是bst inorder traverse。起點就是BST里最小的值,也就是leftmost.
public class BSTIterator { ArrayDequestk; public BSTIterator(TreeNode root) { stk = new ArrayDeque (); pushAll(root); } /** @return whether we have a next smallest number */ public boolean hasNext() { return !stk.isEmpty(); } /** @return the next smallest number */ public int next() { TreeNode node = stk.pop(); if(node.right !=null) { pushAll(node.right); } return node.val; } public void pushAll(TreeNode node){ while(node != null){ stk.push(node); node = node.left; } } }
新增了預處理的方法。這個方法的好處就是每次next()都是嚴格的O(1), 而上面那個方法只是AVE O(1).
public class BSTIterator { ArrayListascending; int pos = 0; public BSTIterator(TreeNode root) { ascending = new ArrayList (); inorder(root, ascending); } /** @return whether we have a next smallest number */ public boolean hasNext() { return pos < ascending.size(); } /** @return the next smallest number */ public int next() { return ascending.get(pos++); } public void inorder(TreeNode root, ArrayList ascending){ if(root == null) return; inorder(root.left, ascending); ascending.add(root.val); inorder(root.right, ascending); } }
LC 230 Kth Smallest Element in a BST
返回BST里第k小的元素。 強提示:有序。
從leftmost開始,找到第k個點返回。時間復雜度近似到O(K).
為了寫代碼的清晰度,我們使用recursion的方法做inorder traversal。
public class Solution { public int kthSmallest(TreeNode root, int k) { if(root == null) return 0; int[] res = {Integer.MIN_VALUE}; kthSmallest(root, k, res); return res[0]; } public int kthSmallest(TreeNode root, int k, int[] res){ if(res[0] != Integer.MIN_VALUE || root == null){ //if finded kth, all recursion will immediately return to root. return 0; } int left = kthSmallest(root.left, k,res); if(left == k-1){ res[0] = root.val; } int right = kthSmallest(root.right, k - left -1, res); return left + right + 1;
LC99 Recover Binary Search Tree
Two elements of a binary search tree (BST) are swapped by mistake.
如果BST中有兩個節點位置互相交換了,怎么辦? 表明BST的順序被打亂。我們需要找出被打亂的點并返回正確結果。
利用上面給的BST的圖,我們swap(20, 90),得到如下BST:
60 / 40 80 / / 90 50 70 20 / 10 30 100
inorder traversal result is:
10 90 30 40 50 60 70 80 20 100
this is not an ascending array.
90 >30, 80 >20 這兩處順序不合理,靠前的值大于靠后的值。
所以這里我們在inorder traversal的同時,我們還需要比較pre.val和cur.val。
然后將兩個不正確的點記錄下來,最后swap回原來正確的值。
public class Solution { private TreeNode firstNode = null; private TreeNode secondNode = null; private TreeNode preNode = new TreeNode(Integer.MIN_VALUE); public void recoverTree(TreeNode root) { if(root == null) return; inorderTraversal(root); int temp = firstNode.val; firstNode.val = secondNode.val; secondNode.val = temp; } public void inorderTraversal(TreeNode root){ if(root == null) return; inorderTraversal(root.left); if(firstNode == null && preNode.val > root.val) { firstNode = preNode; } if(firstNode != null && preNode.val > root.val) { secondNode = root; } preNode = root; inorderTraversal(root.right); } }
LC450 Delete Node in a BST
找到一個點容易,利用root.left.val < root.val < root.right.val,時間復雜度O(logN)找到。
刪除一個點。如果是葉子節點,或者只有一個子樹。都容易操作。
如果是中間節點怎么辦?我們找到它在bst里的前一個點(或者后一個點),改變要刪除節點的值,然后刪除它的前一個點。
思想來自于heap的代碼實現。我們每次Pop的時候取的是根節點的值,然后把heap里最尾端的點換到根節點,然后shift down。
public class Solution { public TreeNode deleteNode(TreeNode root, int key) { if(root == null) return null; if(key < root.val) { root.left = deleteNode(root.left, key); } else if(key > root.val) { root.right = deleteNode(root.right, key); } else { if(root.left == null) { return root.right; } else if(root.right == null) { return root.left; } TreeNode node = findNextMin(root.right); root.val = node.val; root.right = deleteNode(root.right, node.val); } return root; } public TreeNode findNextMin(TreeNode node) { while(node.left != null) { node = node.left; } return node; } }
寫不下了,換一篇,點這里:
https://segmentfault.com/a/11...
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://m.specialneedsforspecialkids.com/yun/66574.html
摘要:當我們希望查詢時,則從根節點開始尋找其所在的區間,如果位于左側區間,則查詢左子樹啊,如果位于右側區間,則查詢右子樹。如果橫跨了分割點,則分別查詢左子樹的部分和右子樹的部分。 題目要求 You are given an integer array nums and you have to return a new counts array. The counts array has t...
摘要:題目鏈接的題,用來做,這種求有多少的題一般都是。里多加一個信息表示以為的節點數。也可以做,因為是統計有多少的,其實就是求從最小值到的。的是,要做一個映射,把的值映射到之間。所以先把給一下,用一個來做映射。還有的方法,參考 315. Count of Smaller Numbers After Self 題目鏈接:https://leetcode.com/problems... divi...
摘要:復雜度思路每遍歷到一個數,就把他到已有的中。對于每一個,維護一個和一個自身的數目。比如,然后每次遍歷到一個數,就把對應位置的值加一。比如碰到之后,就變成,然后統計的和。 Leetcode[315] Count of Smaller Numbers After Self ou are given an integer array nums and you have to return a...
摘要:我們建立的,其中解決重復值的問題,記錄左子樹的節點數。給定要找的點,這里的規律就是,往右下走,說明當前點和當前的的左子樹的值全部比小。我們走到要向右,這是左子樹沒變化,這里也不變。 題目細節描述參看leetcode。 今天的重頭戲 LC315 Count of Smaller Numbers After Self.在講這個題目之前,請思考這個問題。在BST找到所有比Node P小的節點...
Problem You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i]. Exam...
閱讀 2155·2023-04-26 00:38
閱讀 1941·2021-09-07 10:17
閱讀 894·2021-09-02 15:41
閱讀 644·2021-08-30 09:45
閱讀 549·2019-08-29 17:25
閱讀 3218·2019-08-29 15:07
閱讀 2198·2019-08-29 12:52
閱讀 3741·2019-08-26 13:35