无法找到树中的所有模式

Question

我想解决以下算法问题。

给定一个有重复的二元搜索树（BST），找到所有模式（s）（最常出现的元素）在给定的BST。 假设一个BST定义如下。 节点的左子树只包含键值小于或等于该节点键值的节点。 节点的右子树只包含键大于或等于节点的键的节点。 左子树和右子树也都必须是二元搜索树。

例如 给定BST [1,null,2,2],

   1
    \
     2
    /
   2

返回[2]。

注意：如果一棵树有多个模式，可以按任意顺序返回。 追问：你能不能不使用任何额外的空间？你能在不使用任何额外空间的情况下做到这一点吗？假设由于递归而产生的隐含栈空间不算在内）。

我写了以下代码，但最后一个测试用例没有通过。

class TreeNode {
    constructor(val, left, right) {
        this.val = (val === undefined ? 0 : val)
        this.left = (left === undefined ? null : left)
        this.right = (right === undefined ? null : right)
    }
}
//updated code, doesn't seem to work, not sure if I am editing it the way it is suggested.
const findMode = root => {
    if (!root) return []
    if (root && !root.left && !root.right) return [root.val]
    const hash = {}
    let current = root
    let result = []
    let keys

    const dfs = c => {
        if (!c) return
        if (c.left) dfs(c.left)
        hash[c.val] = (hash[c.val] || 0) + 1
        if (c.right) dfs(c.right)
    }
    dfs(current)
    // keys = Object.keys(hash)
    // if (keys.length <= 1) return [+keys]
    // else keys.reduce((a, b) => {
    //     if (hash[a] === hash[b]) result.push(+a, +b)
    //     else if (hash[a] > hash[b]) {
    //         result.push(+a)
    //     } else result.push(+b)
    // })
    // return result
    keys = Object.keys(hash);
    keys.sort((a, b) => hash[b] - hash[a]);
    keys.forEach(key => {
        if (hash[key] === keys[0]) result.push(key);
    })
    return result
}

以下是测试用例

const tree = new TreeNode(1, null, new TreeNode(2, new TreeNode(2)))
console.log(findMode(tree)) //[2]

const tree2 = new TreeNode(1, null, new TreeNode(2))
console.log(findMode(tree2)) //[1,2]

const tree3 = new TreeNode(2147483647)
console.log(findMode(tree3)) //[2147483647]

const tree4 = new TreeNode(1, new TreeNode(1))
console.log(findMode(tree4)) // should be [1], but is []

我做错了什么？

Answer 1

如果是 const tree4 = new TreeNode(1, new TreeNode(1)) 你的哈希值只有一个键，而且 reduce 在单元素数组上没有意义。参见 这个.

在单元素数组的情况下，你可以像下面这样做。

if ( Object.keys(hash).length <= 1 ) return Object.keys(hash)

我不认为 reduce 是这里的正确做法。你需要按照键值的递减顺序进行排序，取最高的键，如下图。

var keys = Object.keys(hash);
keys.sort((a,b) => hash[b]-hash[a]);
keys.forEach( key => {
    if ( hash[key] === hash[keys[0]] ) result.push(key);
})
return result