Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

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

Open
qiufeihong2018 opened this issue Aug 29, 2019 · 2 comments
Open

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

qiufeihong2018 opened this issue Aug 29, 2019 · 2 comments

Comments

@qiufeihong2018
Copy link

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

qiufeihong2018 commented Aug 29, 2019

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

@ConardLi
Copy link
Owner

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants