레벨 주문 순회 이진 트리 문제

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와 함께이 문제를 해결했습니다. 그러나, 나는 그것을 다른 방법으로 해결하려고 노력할 수 없었습니다. 나는 위의에서

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 

:

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

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

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

이 여기 어딘가에 코드 []에 반환되고 있기 때문에 분명하지만, 내 코드 것 : 아래는 내 출력 대 샘플 입력/올바른 출력은 < < 대신 + =를 사용하여 [] 케이스를 처리하고 하나의 arr이 비어 있으면 병합 기능이 작동합니다. 여기서 생각할 것은 왼쪽과 오른쪽 모두에 대한 레벨 순서 트래버스의 각 레벨을 병합 한 다음 배열의 시작 부분에 루트를 삽입한다는 것입니다.

또한 루트가 빈 배열로 삽입 될 수 있다고 생각했는데 루트가 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 

이 나무를 구축 피할 것이며, 재귀보다 효율적입니다.