javascript - 使用 Javascript 的二叉树级顺序遍历

Question

这是一个leetcode问题。

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example:Given binary tree [3, 9, 20, null, null, 15, 7],

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

但我正在尝试一种新的 JavaScript 方式，而不是完全按照他们的解决方案。到目前为止，我能够打印数组，但是

How can different levels be printed in new rows

到目前为止，以下是我的代码:

var levelOrder = function(root) {
let output = [];
let queue = [];
let currentNode = root;
queue.push(currentNode);
let currentLevel = 1;
while(queue.length){
    
    currentNode = queue.shift();
    currentLevel--; //this will ensure we are adding new lines only on next level
    output.push(currentNode);
    
    if(currentNode.left){
        queue.push(currentNode.left);
    }
    if(currentNode.right){
        queue.push(currentNode.right);
    }
    
    if(currentLevel = 0){
        output = output + '/n'; //Insert a new line
        currentLevel = queue.length; //2
    }
}
return output;
};

Input: [3,9,20,null,null,15,7],

Expected Output:
[
[3],
[9,20],
[15,7]
]

LeetCode 问题链接:
BinaryTreeTraversalUsingBFS

Answer 1

我想你快到了。不知道是什么output = output + '/n';虽然是为了。
这会通过:

var levelOrder = function(root) {
    const levels = []

    if(!root) {
        return levels
    }

    const queue = [root]
    while (queue.length){
       const queueLength = queue.length
       const level = []

       for(let i = 0; i < queueLength; i++){

           const node = queue.shift()

           if(node.left){
               queue.push(node.left)
           }
           if(node.right){
               queue.push(node.right)
           }

           level.push(node.val)
       }
       levels.push(level)
   }
    return levels
}

引用

更多详情，您可以查看Discussion Board .有很多公认的解决方案，有多种 languages和解释，高效的算法，以及渐近的time/space复杂性分析1 , 2在那里。