Невозможно найти все моды в дереве - PullRequest
Новая
       44

Невозможно найти все моды в дереве

0 голосов
/ 04 мая 2020

Я пытаюсь решить следующую проблему с алгоритмами:

Учитывая двоичное дерево поиска (BST) с дубликатами, найти все режимы (наиболее часто встречающийся элемент) в учитывая BST. Предположим, что BST определяется следующим образом: Левое поддерево узла содержит только узлы с ключами, меньшими или равными ключу узла. Правое поддерево узла содержит только узлы с ключами, которые больше или равны ключу узла. И левое, и правое поддеревья также должны быть бинарными деревьями поиска.

Например: задано BST [1, null, 2,2], 

   1
    \
     2
    /
   2

return [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 []

Что я делаю не так?

1 Ответ

1 голос
/ 04 мая 2020

В случае const tree4 = new TreeNode(1, new TreeNode(1)) ваш ха sh имеет только один ключ, а reduce не имеет смысла для одного элемента массива. См. this .

. В случае одноэлементного массива вы можете сделать что-то вроде следующего:

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
...