力扣 230. 二叉搜索树中第K小的元素 & 剑指 Offer 54. 二叉搜索树的第k大节点

230题目描述：

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

解析：

递归方法 二叉搜索树特点是左节点值小于根节点，而右节点值大于根节点

1.定义一个函数count计算二叉搜索树左子树的节点个数
2.用k值和左子树节点个数的值比较，分别判断三种情况
第k个元素在根节点上，直接返回根节点的值
第k个元素在左子树上，则返回二叉搜索树左子树节点的值
第k个元素在右子树上，则返回二叉搜索树右子树节点的值

Java:

public int kthSmallest(TreeNode root, int k) {
        int leftCount = count(root.left);
        if(leftCount + 1 == k) {
            return root.val;
        } else if(k <= leftCount) {
            return kthSmallest(root.left, k);
        } else {
            return kthSmallest(root.right, k - leftCount - 1);
        }
    }
    public int count(TreeNode root) {
        if(root == null) {
            return 0;
        }
        return count(root.left) + count(root.right) + 1;
    }

JavaScript:

var kthSmallest = function(root, k) {
    let leftCount = count(root.left);
    if(leftCount + 1 === k) {
        return root.val;
    } else if(k <= leftCount) {
        return kthSmallest(root.left, k);
    } else {
        return kthSmallest(root.right, k - leftCount - 1);
    }
    function count(root) {
        if(root === null) {
            return 0;
        }
        return count(root.left) + count(root.right) + 1;
    }
};

54题目描述：

给定一棵二叉搜索树，请找出其中第k大的节点。

解析：

同上一题

Java:

public int kthLargest(TreeNode root, int k) {
        int rightCount = count(root.right);
        if(rightCount + 1 == k) {
            return root.val;
        } else if(k <= rightCount) {
            return kthLargest(root.right, k);
        } else {
            return kthLargest(root.left, k - rightCount - 1);
        }
    }
    public int count(TreeNode root) {
        if(root == null) {
            return 0;
        }
        return count(root.left) + count(root.right) + 1;
    }

JavaScript:

var kthLargest = function(root, k) {
    let rightCount = count(root.right);
    if(rightCount + 1 === k) {
        return root.val;
    } else if(k <= rightCount) {
        return kthLargest(root.right, k);
    } else {
        return kthLargest(root.left, k - rightCount - 1);
    }
    function count(root) {
        if(root === null) {
            return 0;
        }
        return count(root.left) + count(root.right) + 1;
    }
};