二叉搜索树的第k大节点
给定一棵二叉搜索树，请找出其中第k大的节点。
示例
输入: root = [3,1,4,null,2], k = 1
3
/ \
1 4
\
2
输出: 4
思路
方案一： 利用中序遍历，把所有的值放到一个数组里面，遍历结束后，返回arr[arr.length-k]，即是所求。
方案二： 利用逆中序遍历（右-根-左）,依次k–，当k等于0，说明已经达到第k大的节点了，这个节点即是所求
代码
// 方案1代码
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @param {number} k
* @return {number}
*/
var kthLargest = function(root, k) {
if (root == null) {
return null;
}
const res = inOrderTraverse(root);
return res[res.length - k];
};
function inOrderTraverse(root, arr = []) {
root.left && inOrderTraverse(root.left, arr);
arr.push(root.val);
root.right && inOrderTraverse(root.right, arr);
return arr;
}
方案二代码：
function kthLargest(root, k) {
if (root === null || k === 0) {
return null;
}
let max = null;
function kthLargestCore(root) {
if (!root) return;
kthLargestCore(root.right);
if (--k === 0) {
return max = root.val;
}
kthLargestCore(root.left);
}
kthLargestCore(root);
return max;
}
复杂度分析:
方案一：
- 时间复杂度: O(N)
- 空间复杂度：O(N)
方案二：
- 时间复杂度: O(N)
- 空间复杂度：O(1)