Возникли проблемы с итеративным решением бинарного дерева для получения суммы путей, равной целевой сумме - PullRequest
Новая
       60

Возникли проблемы с итеративным решением бинарного дерева для получения суммы путей, равной целевой сумме

0 голосов
/ 28 апреля 2020

Цель описана в этой задаче:

Вам дано двоичное дерево, в котором каждый узел содержит целочисленное значение. Найдите количество путей, которые суммируются с данным значением. Путь не должен начинаться или заканчиваться на root или листе, но он должен go вниз (проходить только от родительских узлов к дочерним узлам). Дерево имеет не более 1000 узлов, а значения находятся в диапазоне от -1 000 000 до 1000 000.

Пример: root = [10,5, -3,3,2, ноль, 11, 3, -2, ноль, 1], сумма = 8 

          10
         /  \
        5   -3
       / \    \
      3   2   11
     / \   \
    3  -2   1

Возврат 3. Пути, сумма которых равна 8:

  1. 5 -> 3
  2. 5 -> 2 -> 1
  3. -3 -> 11

Я написал следующий код, который хочу решить итеративно, не используя рекурсию, однако я не могу получить правильное количество и не могу найти ошибку в моей логике c. 

class TreeNode {
    constructor(val) {
        this.val = val;
        this.left = this.right = null;
    }
}


const pathSum = (root, sum) => {
    if (!root) return 0
    let totals = [root]
    let queue = [root]
    let count = 0
    let current

    while (queue.length) {
        current = queue.shift()
        if (current.val === sum) count++
        for (let s of totals) {
            if (s.val + current.val === sum) count++
        }
        if (current.left) queue.push(current.left), totals.push(current.left)
        if (current.right) queue.push(current.right), totals.push(current.right)
    }
    return count
}

const tree = new TreeNode(10)
tree.left = new TreeNode(5)
tree.right = new TreeNode(-3)

tree.left.left = new TreeNode(3)
tree.left.right = new TreeNode(2)
tree.left.right = new TreeNode(2)
tree.right.right = new TreeNode(11)

tree.left.left.left = new TreeNode(3)
tree.left.left.right = new TreeNode(-2)
tree.left.right.right = new TreeNode(1)

console.log(pathSum(tree, 8))

Буду признателен, если у кого-то есть предложения, чтобы код работал итеративно.

...