Попытка возврата уровня порядка двоичного дерева - PullRequest
Новая
       28

Попытка возврата уровня порядка двоичного дерева

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

У меня есть следующий код, который я разработал на доске, и в соответствии с этим шагом он дает мне правильный результат; однако запуск его на компьютере доказывает обратное. Код выглядит следующим образом: 

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

const levelOrderBottom = root => {
    let visited = []
    if (!root) return visited
    let queue = [root, 's']
    let current
    let row = []

    while (queue.length > 1) {
        current = queue.shift()
        if (current === 's') {
            visited.unshift(row)
            row = []
            queue.push('s')
        } else {
            if (current.left) queue.push(current.left)
            if (current.right) queue.push(current.right)
            row.push(current.val)
        }
    }
    return visited
}

//example 1
const tree1 = new TreeNode(3)
tree1.left = new TreeNode(9)
tree1.right = new TreeNode(20)
tree1.right.left = new TreeNode(15)
tree1.right.right = new TreeNode(7)

console.log(levelOrderBottom(tree1)) //[ [15,7], [9,20], [3] ]

Дерево и выходные данные должны выглядеть следующим образом 

Given binary tree [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
return its bottom-up level order traversal as:
[
  [15,7],
  [9,20],
  [3]
]

Однако я получаю только [ [9,20] ,[3] ]. Я не могу определить недостатки в моей логике c. Есть мысли, что я делаю не так?

Ответы [ 3 ]

1 голос
/ 10 апреля 2020

Вы можете сохранить уровень и назначить ему уровень. 

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

const levelOrderBottom = root => {
    let visited = []
    if (!root) return visited
    let queue = [[root, 0]]

    while (queue.length) {
        let [current, level] = queue.shift()
        if (!visited[level]) visited[level] = []
        if (current.left) queue.push([current.left, level + 1])
        if (current.right) queue.push([current.right, level + 1])
        visited[level].push(current.val)
    }
    
    return visited.reverse()
}

//example 1
const tree1 = new TreeNode(3)
tree1.left = new TreeNode(9)
tree1.right = new TreeNode(20)
tree1.right.left = new TreeNode(15)
tree1.right.right = new TreeNode(7)

console.log(levelOrderBottom(tree1)) //[ [15,7], [9,20], [3] ]
1 голос
/ 10 апреля 2020

Вы не вызываете visited.unshift(row) в конце, когда queue.length == 1, несмотря на то, что row все еще содержит результаты, которые вы хотите добавить.

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

Когда вам нужно разделиться на уровни, вам не нужно использовать очередь: 

const levelOrderBottom = root => {
  let visited = []
  let row = root ? [root] : []
  while(row.length > 0) {
    visited.unshift(row.map(n => n.val))
    row = row
      .flatMap(n => [n.left, n.right])
      .filter(n => n!=null);
  }
  return visited
}
...