Kth Smallest Element in a BST

Barry_Ng 发布于2019-08-14 17:26 / 1082人阅读

摘要：题目链接二分找结果，按左边数来分如果改下，加入的，那就可以在时间内找到结果了

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

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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