как получить разницу между двумя значениями или узлами в javascript - PullRequest
Новая
       65

как получить разницу между двумя значениями или узлами в javascript

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

Я пытаюсь решить эту проблему. Я не получаю ожидаемого результата

Учитывая дерево двоичного поиска (BST) с узлом root root, вернуть минимальную разницу между значениями любого два разных узла в дереве.

Пример:

Ввод: 

root = [4,2,6,1,3,null,null]

Выход: 

1

Пояснение:

Обратите внимание, что root - это объект TreeNode, а не массив.

Данное дерево [4 , 2,6,1,3, null, null] представлен следующей диаграммой: 

      4
    /   \
  2      6
 / \    
1   3

хотя минимальная разница в этом дереве равна 1, она возникает между узлом 1 и узлом 2, а также между узел 3 и узел 2.

Я пробовал вот так 

var minDiffInBST = function (root) {
    let min = Number.MAX_VALUE
    const getMin = (node) => {
        if (node.left && node.right) {
            console.log('both')
            return Math.min(node.val - node.left.val, node.right.val - node.val)
        } else if (node.right) {
            console.log('right')
            return node.right.val - node.val
        } else if (node.left) {
            console.log('left')
            return node.val - node.left.val
        } else {
            return Number.MAX_VALUE
        }
    }

    const preOrder = (root) => {
        if (!root) {
            return 0;
        }
        let x = getMin(root)
        if (x < min)
            min = x
        preOrder(root.left)
        preOrder(root.right)

    }
    preOrder(root)
    return min
};

console.log(minDiffInBST({
        "val": 90,
        "left": {
            "val": 69,
            "left": {"val": 49, "left": null, "right": {"val": 52, "left": null, "right": null}},
            "right": {"val": 89, "left": null, "right": null}
        },
        "right": null
    }

))

Получение вывода 3 ожидаемый результат 1

вопрос Я взято отсюда https://leetcode.com/problems/minimum-distance-between-bst-nodes/

1 Ответ

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

Вам необходимо выполнить обход заказа, а не обход предварительного заказа.

В BST обход по порядку дает вам отсортированный список. В отсортированном списке минимальное расстояние между двумя элементами будет наиболее близким друг к другу.

Итак, сначала решите это для отсортированного списка, а затем решите его для пройденного BST IN ORDER

...