水平顺序遍历二进制树问题

Question

问题语句：

给定二进制树，返回其节点的级别顺序遍历' 值。（即，从左到右，按级别按级别）。

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

我已经用BFS解决了这一点，这是最直观的方法。但是，我尝试以另一种方式解决它，但我无法做到。以下是示例输入/正确输出与我的输出：

Your input
[3,9,20,null,null,15,7]
Your answer
[[3],[[9],[],[20],[[15],[],[7],[]]]]
Expected answer    
[[3],[9,20],[15,7]]

这显然是因为返回了代码[]中的某个地方，但这是我的代码：

def level_order(root)
    return [] if root.nil?
    arr = merge([level_order(root.left)], [level_order(root.right)]) #this returns an empty arr if both of those are nil..
    arr.insert(0, [root.val]) 
end
def merge(arr1, arr2)
    i = j = 0
    while i < arr1.length && j < arr2.length
        arr1[i] += arr2[j]
        i += 1
        j += 1
    end
    while j < arr2.length #check if any remaining elements in arr 2
        arr1 << arr2[j]
        j += 1
    end
    arr1
end

在上面，我通过 =而不是＆lt;＆lt;处理[]情况。如果一个ARR为空，则合并函数有效。这里的想法是，我正在为左侧和右侧的级别顺序遍历的每个级别合并，然后在数组的开头插入根。

我还认为可以将根可以插入一个空数组，但这不可能发生，因为我有一个初始返回语句，如果root为nil，则称为。有什么想法吗？

Answer 1

它应该像更改此

一样简单

arr = merge([level_order(root.left)], [level_order(root.right)]) 

to

arr = merge(level_order(root.left), level_order(root.right))

但是，我的写作会有些不同：

input = [3,9,20,nil,nil,15,7]
output = []
start  = 0
length = 1
while start < input.length do
  output << input.slice(start, length).compact
  start  += length
  length *= 2  
end
puts output.inspect

这将避免建造树，并且比递归更有效。