查找二叉树

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 

他们都是差不多的速度，确实是第一个更容易阅读和理解。