Kth Smallest Element in a BST

Barry_Ng 發布于2019-08-14 17:26 / 1083人閱讀

摘要：題目鏈接二分找結果，按左邊數來分如果改下，加入的，那就可以在時間內找到結果了

Kth Smallest Element in a BST

題目鏈接：https://leetcode.com/problems...

inorder traverse：

public class Solution {
    public int kthSmallest(TreeNode root, int k) {
        // morris: inorder traverse
        TreeNode cur = root, prev = null;
        int count = 0;
        while(cur != null) {
            // reach the end of left part
            if(cur.left == null) {
                if(++count == k) return cur.val;
                cur = cur.right;
            }
            else {
                prev = cur.left;
                // find the right most part
                while(prev.right != null && prev.right != cur) prev = prev.right;
                // reach the end of current right part
                if(prev.right == null) {
                    prev.right = cur;
                    cur = cur.left;
                }
                // recover the tree
                else {
                    prev.right = null;
                    if(++count == k) return cur.val;
                    cur = cur.right;
                }
            }
        }
        
        return -1;
    }
}

二分找結果，按左邊nodes數來分：

public class Solution {
    public int kthSmallest(TreeNode root, int k) {
        int left = getNum(root.left);
        if(left == k - 1) return root.val;
        else if(left < k - 1) return kthSmallest(root.right, k - left - 1);
        else return kthSmallest(root.left, k);
    }
    
    private int getNum(TreeNode node) {
        if(node == null)  return 0;
        // divide and conquer
        return 1 + getNum(node.left) + getNum(node.right);
    }
}

如果改下node，加入number of left的field，那就可以在O(h)時間內找到結果了：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     int leftNum;
 *     TreeNode(int x, int num) { val = x; leftNum = num; }
 * }
 */
public class Solution {
    public int kthSmallest(TreeNode root, int k) {
        int left = root.leftNum;
        if(left == k - 1) return root.val;
        else if(left < k - 1) return kthSmallest(root.right, k - left - 1);
        else return kthSmallest(root.left, k);
    }
}

GPU云服務器云服務器 Kth Smallest BST Element

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/66636.html

[Leetcode] Kth Smallest Element in a BST 二叉搜索樹第k小節

摘要：中序遍歷復雜度時間空間思路因為左節點小于根節點小于右節點，二叉搜索樹的一個特性就是中序遍歷的結果就是樹內節點從小到大順序輸出的結果。這里采用迭代形式，我們就可以在找到第小節點時馬上退出。這樣我們就可以用二叉樹搜索的方法來解決這個問題了。 Kth Smallest Element in a BST Given a binary search tree, write a function...

Dean 2019-08-14 12:26 評論0 收藏0
[Leetcode-Tree] Kth Smallest Element in a BST

摘要：解題思路本題需要找的是第小的節點值，而二叉搜索樹的中序遍歷正好是數值從小到大排序的，那么這題就和中序遍歷一個情況。 Kth Smallest Element in a BSTGiven a binary search tree, write a function kthSmallest to find the kth smallest element in it. Note: You ...

Carl 2019-08-16 10:26 評論0 收藏0
leetcode 315 Count of Smaller Numbers After Self 以

摘要：題目意思就是要一個個的返回當前的最小值。所以解法自然就是。我們需要找出被打亂的點并返回正確結果。然后將兩個不正確的點記錄下來，最后回原來正確的值。如果是葉子節點，或者只有一個子樹。思想來自于的代碼實現。跳過總結請點這里：https://segmentfault.com/a/11... BST最明顯的特點就是root.left.val < root.val < root.right.v...

inapt 2019-08-14 17:20 評論0 收藏0
[LeetCode] 378. Kth Smallest Element in a Sorted M

摘要：先放一行，或一列把堆頂的最小元素取出來，取次，如果該有下一行下一列的，放入堆中最小的個元素已經在上面的循環被完了，下一個堆頂元素就是 Problem Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in...

Shihira 2019-08-16 13:43 評論0 收藏0
378. Kth Smallest Element in a Sorted Matrix

Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.Note that it is the kth smallest element in the sorted order, not the...

makeFoxPlay 2019-08-14 18:13 評論0 收藏0