层序遍历二叉树问题

Question

问题陈述：

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

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

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

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

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

这显然是因为代码 [] 中的某处正在 returned，但这是我的代码：

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

在上面，我通过执行 += 而不是 << 来处理 [] 情况，并且如果一个 arr 为空，则合并功能有效。这里的想法是，我将左右两侧的级别顺序遍历的每个级别合并，然后在数组的开头插入根。

我还考虑过可以将根作为空数组插入，但这不可能发生，因为我有一个初始 return 语句，如果根为 nil 则调用该语句。有什么想法吗？

Answer 1

改这个应该很简单

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

到

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

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

层序遍历二叉树问题

Level Order Traversal Binary Tree Issue

ruby

algorithm

recursion

binary-tree

tree-traversal