尝试return二叉树的层序遍历

Question

我在白板上编写了以下代码，根据该步骤，它给出了正确的结果；然而，运行它在计算机上证明并非如此。代码如下：

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] ]。我无法指出我逻辑中的缺陷。关于我做错了什么，有什么想法吗？

Answer 1

尽管 row 仍然包含您要添加的结果，但您最终没有在 queue.length == 1 时调用 visited.unshift(row)。

Answer 2

您可以存储一个级别并分配给该级别。

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

Answer 3

需要分层次时，不需要使用队列：

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
}

尝试return二叉树的层序遍历

Trying to return a level order traversal of a binary tree

javascript

arrays

algorithm

tree

traversal