Ebene Bestellen Traversal Binary Tree Ausgabe

Question

Problemstellung:

Da Werte ein binärer Baum, bringen Sie das Niveau, um Traversal seiner Knoten. (von links nach rechts, Ebene für Ebene).

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

habe ich dies mit BFS gelöst, die die intuitive Art und Weise, dies zu tun. Allerdings habe ich versucht, es auf eine andere Weise zu lösen, und ich kann es nicht. Im Folgenden finden Sie Abtastwerteingang/korrekte Ausgabe vs. meiner Ausgabe:

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

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

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

Dies ist offensichtlich, weil irgendwo im Code [] zurückgegeben wird, aber mein Code hier vor sich:

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 

Im obigen I behandelt mit [] case by doing + = statt < < und die merge-funktion funktioniert, wenn ein arr leer ist. Die Idee hier ist, dass ich jede Ebene der Level-Reihenfolge Traversal für beide linken und rechten Seiten zusammenführen, dann die Wurzel an den Anfang des Arrays einfügen.

Ich dachte auch, dass die Wurzel als ein leeres Array eingefügt werden könnte, aber das kann nicht passieren, weil ich eine erste Return-Anweisung habe, die aufgerufen wird, wenn root ist Null. Irgendwelche Ideen?

Answer 1

Es sollte so einfach sein wie die Veränderung dieses

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

Um

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

aber ich würde das etwas anders geschrieben habe:

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 

Dies würde vermeiden, einen Baum zu bauen und wäre effizienter als Rekursion.