awesome-coding-js
awesome-coding-js copied to clipboard
问题:二叉搜索树的第k个节点
递归算法:好像写错了,解法思路是对的,但是运行就报错, 运行环境:vscode集成leetcode插件
/*
* @lc app=leetcode.cn id=230 lang=javascript
*
* [230] 二叉搜索树中第K小的元素
*/
/**
* 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}
*/
function kthSmallest(root, k) {
const arr = [];
loopThrough(root, arr);
if (k > 0 && k <= arr.length) {
return arr[k - 1];
}
return null;
}
function loopThrough(node, arr) {
if (node) {
loopThrough(node.left, arr);
arr.push(node);
loopThrough(node.right, arr);
}
}
✘ Wrong Answer
✘ 0/91 cases passed (N/A)
✘ testcase: '[3,1,4,null,2]\n1'
✘ answer: NaN
✘ expected_answer: 1
✘ stdout:
@ConardLi
/*
* @lc app=leetcode.cn id=230 lang=javascript
*
* [230] 二叉搜索树中第K小的元素
*/
/**
* 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}
*/
function kthSmallest(root, k) {
let res
function middle(node) {
if (node) {
middle(node.left)
if (--k === 0) {
res = node.val
}
middle(node.right)
}
}
middle(root)
return res
};
换成这种写法就可以成功,但是道理是一样啊,就是中序遍历的时候一个塞进数组查找最小值,一个k自减找到最小值,为什么前者报错,难道是leetcode插件有问题?求解
这个出错的case我在本地跑了一下没问题,到leetcode上输出是NaN,我也很奇怪。