230. 二叉搜索树中第K小的元素

一、题目描述

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。

示例 1：

输入：root = [3,1,4,null,2], k = 1
输出：1

示例 2：

输入：root = [5,3,6,2,4,null,null,1], k = 3
输出：3

二、解题

递归

结点的左子树只包含小于当前结点的数。结点的右子树只包含大于当前结点的数。使用递归方法，先判断左子树的数量，看是否等于k-1，若等于k-1,则说明当前节点正好是需要返回的节点，否则在右子树中查找，k更新为k-leftcnt-1。

class Solution {
    int res = 0;
    int cnt = 0;
    public int kthSmallest(TreeNode root, int k) {
        //这题的一个重点是此树为二叉搜索树 结点的左子树只包含小于当前结点的数。结点的右子树只包含大于当前结点的数。
        //使用递归方法 先判断左子树的数量 看是否等于k-1，若等于k-1,则说明当前节点正好是需要返回的节点，否则在右子树中查找
        int leftcnt = count(root.left);
        if(leftcnt == k-1){
            return root.val;
        }
        //节点在左子树
        if(leftcnt > k-1){
            return kthSmallest(root.left,k);
        }
        //否则在右子树
        return kthSmallest(root.right,k-leftcnt-1);
       
    }
    private int count(TreeNode node) {
        if (node == null) return 0;
        return 1 + count(node.left) + count(node.right);
    }
}

中序遍历

由于是二叉搜索树，所以使用中序遍历，则返回的数直接是升序的，直接遍历到第k个值就是当前值。

class Solution {
    int res = 0;
    int cnt = 0;
    public int kthSmallest(TreeNode root, int k) {
        if(root == null){
            return 0;
        }
        inoeder(root,k);
        return res;
    }
    //中序遍历
    public void inoeder(TreeNode root,int k){
        if(root == null){
            return ;
        }
        inoeder(root.left,k);
        cnt++;
        if(cnt==k){
            res = root.val;
            return ;
        }
        inoeder(root.right,k);
    }
}

最后

以上就是眯眯眼西装为你收集整理的230. 二叉搜索树中第K小的元素的全部内容，希望文章能够帮你解决230. 二叉搜索树中第K小的元素所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。