查找二叉樹

Question

的葉子下面的問題工作：

Given a binary tree, collect a tree's nodes as if you were doing this: Collect and remove all leaves, repeat until the tree is empty. 

Example: 
Given binary tree 
      1 
     /\ 
     2 3 
    /\  
     4 5  
Returns [4, 5, 3], [2], [1]. 

Explanation: 
1. Removing the leaves [4, 5, 3] would result in this tree: 

      1 
     /
     2   
2. Now removing the leaf [2] would result in this tree: 

      1   
3. Now removing the leaf [1] would result in the empty tree: 

      []   
Returns [4, 5, 3], [2], [1]. 

我的想法是如下所示的簡單遞歸算法。這個想法是找到左側子樹和右側子樹的葉子，並將它們編織成深度在右側子樹中。我已經非常徹底地測試了'編織'方法，我認爲它很好。我關心的是我的遞歸實現 - 我正在從正確的答案中獲得答案，並且不知道爲什麼。

下面是我的代碼示例輸入/輸出：

def find_leaves(root) 
    return [] if root.nil? 
    #create leaf_arr of root.left and root.right 
    #weave them in order. 
    #add the root 

    left_arr = find_leaves(root.left) 
    right_arr = find_leaves(root.right) 


    weave(left_arr, right_arr) << [root] 
end 


def weave(arr1, arr2) #these are 2d arrs 
    i = 0 
    until i == arr1.length || i == arr2.length #potential nil/empty case here 
     arr1[i] += arr2[i] 
     i += 1 
    end 
    if i < arr2.length 
     #either arr 1 or arr2 isn't finished. if arr1 isn't finished, we're done. if arr2 isnt finished, do the below: 
     until i == arr2.length 
      arr1 << arr2[i] 
      i += 1 
     end 
    end 
    arr1 
end 

樣品輸入/輸出/正確答案：

Run Code Result: × 

input: [1,2,3,4,5] 

Your answer: [[[4],[5],[3]],[[2,4,5]],[[1,2,3,4,5]]] 

Expected answer: [[4,5,3],[2],[1]] 

我打印的left_arr和right_arr變量，它們的輸出看起來很好，我已經對我的編織算法進行了壓力測試。我在概念上在這裏嗎？

Answer 1

我不能評論，所以我會這樣做。 （請記住我不知道紅寶石） 我認爲雙陣列（root.left和root.right）的定義方式已經出錯了。他們如何定義？如何定義root？

但是，以下eplains整個數組的重複。

weave(left_arr, right_arr) << [root] 

這應該是在這一行。

weave(left_arr, right_arr) << [root.root] 

否則，您將追加整個根數組，即[1,2,3,4,5]。所以這解釋了最後一部分的添加。 [[[4],[5],[3]],[[2,4,5]],[[1,2,3,4,5]]]。

我在尋找在編織誤差會在每個階段打印ARR1和ARR2 .... 你能證明建議..

Answer 2

在你的代碼使用純深度優先搜索算法DFS和用這種算法，我認爲你很難實現你的目標，你在編織函數中進行數組操作。因爲你的樹將被處理的順序4，5，2，3，1 一種解決方案將與迭代做到這一點（僞代碼）：

function doJob(root) begin 
    leaves = findLeaves(root) 
    while leaves.size > 0 do begin 
    for each leaf in leaves delete(leaf) 
    leaves = findLeaves(root) 
    end 
    delete(root) 
end 

function findLeaves(node) begin 
    if node = nil then begin 
    return [] 
    end 
    else begin 
    leftLeaves = findLeaves(node.left) 
    rightLeaves = fingLeaves(node.right) 
    leaves = leftLeaves + rightLeaves 
    if leaves.size == 0 then begin 
     leaves.add(node) 
    end 
    return leaves 
    end 
end 

Answer 3

因爲這仍然坐在開放，似乎公平高度當我谷歌搜索你的標題。我將展示一個漂亮的表現力的解決方案：

def find_leaves(root) 
    return [] if root.nil? 
    return [[root.val]] if root.left.nil? && root.right.nil? 
    todo = [root] 
    leaves = [] 

    until todo.empty? 
    top = todo.shift 
    %w[left right].each do |path| 
     leaf = top.send(path) 
     next if leaf.nil? 
     if leaf.left.nil? && leaf.right.nil? 
     leaves << leaf.val 
     top.instance_variable_set("@#{path}", nil) 
     else 
     todo << leaf 
     end 
    end 
    end 
    [leaves].concat(find_leaves(root)) 
end 

更重構後的版本：

def find_leaves(root) 
    leaves = [] 
    search = lambda do |branch| 
    return -1 unless branch 
    i = 1 + [search[branch.left], search[branch.right]].max 
    (leaves[i] ||= []) << branch.val 
    i 
    end 
    search[root] 
    leaves 
end 

他們都是差不多的速度，確實是第一個更容易閱讀和理解。