xindoo is
always here

Leetcode 230. Kth Smallest Element in a BST

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.
求一个二叉搜索树的第k小值。

题目链接:https://leetcode.com/problems/kth-smallest-element-in-a-bst/

  先来看下二叉搜索树的性质,对于任意一个非叶子节点,它的左子树中所有的值必定小于这个节点的val,右子树中所有的值必定大于或等于当前节点的val。 这条性质就保证了如果我们对二叉搜索树做中序遍历,中序遍历的结果肯定是有序的。对于此题而言,我们只需要拿到中序遍历结果,然后返回第k个即可,时间复杂度是O(n)。
  但是,其实是有更优的解决方案的,我们只需要第k的数,并不需要遍历整个BST。这个时候,我们只需要把中序遍历的递归代码稍作改造即可,加一个全局遍历count来计数当前遍历到第几个数。因为上面所说的性质,中序遍历是有序的,所以只需要在计数器到k时返回当前节点的val,这就是我们需要的结果,时间复杂度O(k)。

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
    private int count = 0;
    public int kthSmallest(TreeNode root, int k) {
        if (root == null)
            return 0;
        int ret=kthSmallest(root.left, k);
        if (0 != ret)
            return ret;
        if(++count == k) 
            return root.val;
        return kthSmallest(root.right, k);
   }
}
打赏
未经允许不得转载:XINDOO » Leetcode 230. Kth Smallest Element in a BST
分享到: 更多 (0)

评论 抢沙发

xindoo

联系我联系我们

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏