[Leetcode每日一题]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

提示：
树中的节点数为 n 。
1 <= k <= n <= 10⁴
0 <= Node.val <= 10⁴

代码:

package leetcodeday1;

public class leetcode230 {
    /**
     * 由于二叉搜索树，左子树一定小于该节点，右子树一定大于该节点，所以我们可以
     * 1。先确定第k小元素的位置，我们可以先得到根节点左子树的数量leftNum
     *      （1）如果k < leftNum，则该元素在根节点的左子树中
     *      （2）如果k = leftNum + 1, 则该元素是根节点
     *      （3）如果k > leftNum + 1, 则该元素在根节点的右子树中
     * 2。确定位置后，我们可以进行递归回溯，即确定后将该节点的左孩子或者右孩子重新作为根节点进行判断
     * 3。结束条件为 情况（2）
     * 
     * 但这样时间复杂度会高很多，因为每次往下都会去统计左子树的元素数量
     */
    public int kthSmallest(TreeNode root, int k) {
        int leftNum = getLeftNum(root.left);
        // 结束条件
        if (leftNum + 1 == k){
            return root.val;
        }
        else if (k <= leftNum){
            return kthSmallest(root.left, k);
        }
        else {
            return kthSmallest(root.right, k - leftNum - 1);
        }
    }

    // 获得左子树中元素的数量
    private int getLeftNum(TreeNode root) {
        // 结束条件
        if (root == null){
            return 0;
        }
        return getLeftNum(root.left) + getLeftNum(root.right) + 1;
    }

}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

最后

以上就是淡定小海豚为你收集整理的[Leetcode每日一题]230. 二叉搜索树中第K小的元素的全部内容，希望文章能够帮你解决[Leetcode每日一题]230. 二叉搜索树中第K小的元素所遇到的程序开发问题。

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