国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

leetcode 315 Count of Smaller Numbers After Self 以

inapt / 3398人閱讀

摘要:題目意思就是要一個個的返回當前的最小值。所以解法自然就是。我們需要找出被打亂的點并返回正確結果。然后將兩個不正確的點記錄下來,最后回原來正確的值。如果是葉子節點,或者只有一個子樹。思想來自于的代碼實現。

跳過總結請點這里:
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 {
    ArrayDeque stk;
    
    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 {
    ArrayList ascending;
    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

相關文章

  • leetcode315. Count of Smaller Numbers After Self

    摘要:當我們希望查詢時,則從根節點開始尋找其所在的區間,如果位于左側區間,則查詢左子樹啊,如果位于右側區間,則查詢右子樹。如果橫跨了分割點,則分別查詢左子樹的部分和右子樹的部分。 題目要求 You are given an integer array nums and you have to return a new counts array. The counts array has t...

    elarity 評論0 收藏0
  • 315. Count of Smaller Numbers After Self

    摘要:題目鏈接的題,用來做,這種求有多少的題一般都是。里多加一個信息表示以為的節點數。也可以做,因為是統計有多少的,其實就是求從最小值到的。的是,要做一個映射,把的值映射到之間。所以先把給一下,用一個來做映射。還有的方法,參考 315. Count of Smaller Numbers After Self 題目鏈接:https://leetcode.com/problems... divi...

    cnio 評論0 收藏0
  • Leetcode[315] Count of Smaller Numbers After Self

    摘要:復雜度思路每遍歷到一個數,就把他到已有的中。對于每一個,維護一個和一個自身的數目。比如,然后每次遍歷到一個數,就把對應位置的值加一。比如碰到之后,就變成,然后統計的和。 Leetcode[315] Count of Smaller Numbers After Self ou are given an integer array nums and you have to return a...

    dack 評論0 收藏0
  • leetcode 315 Count of Smaller Numbers After Self

    摘要:我們建立的,其中解決重復值的問題,記錄左子樹的節點數。給定要找的點,這里的規律就是,往右下走,說明當前點和當前的的左子樹的值全部比小。我們走到要向右,這是左子樹沒變化,這里也不變。 題目細節描述參看leetcode。 今天的重頭戲 LC315 Count of Smaller Numbers After Self.在講這個題目之前,請思考這個問題。在BST找到所有比Node P小的節點...

    Little_XM 評論0 收藏0
  • [LeetCode] 315. Count of Smaller Numbers After Sel

    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...

    FingerLiu 評論0 收藏0

發表評論

0條評論

最新活動
閱讀需要支付1元查看
<