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

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

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

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

/**
 * Definition for a binary tree node.
 * public 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;
 *     }
 * }
 */
class Solution {
    public int kthSmallest(TreeNode root, int k) {
        int count = countNodes(root.left);
        if (k <= count) {
            return kthSmallest(root.left, k);
        } else if (k > count + 1) {
            return kthSmallest(root.right, k  - 1 -  count);
        }
         return root.val;
    }
    public int countNodes(TreeNode n) {
        if (n == null)
            return 0;
        return 1 + countNodes(n.left) + countNodes(n.right);
    }
}

最后

以上就是轻松小蝴蝶最近收集整理的关于230. 二叉搜索树中第K小的元素230. 二叉搜索树中第K小的元素的全部内容，更多相关230.内容请搜索靠谱客的其他文章。