awesome-coding-js icon indicating copy to clipboard operation
awesome-coding-js copied to clipboard

问题:二叉搜索树的第k个节点

Open qiufeihong2018 opened this issue 6 years ago • 2 comments

递归算法:好像写错了,解法思路是对的,但是运行就报错, 运行环境: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:

qiufeihong2018 avatar Aug 29 '19 01:08 qiufeihong2018

@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插件有问题?求解

qiufeihong2018 avatar Aug 29 '19 02:08 qiufeihong2018

这个出错的case我在本地跑了一下没问题,到leetcode上输出是NaN,我也很奇怪。

ConardLi avatar Aug 29 '19 07:08 ConardLi