ruby - 查找二叉树的叶子

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

我无法发表评论，所以我会这样做。 (请记住我不认识 ruby​​) 我认为双数组(root.left 和 root.right)的定义方式已经出了问题。它们是如何定义的？根是如何定义的？

但是下面解释了整个数组的重复。

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

我在查找 weave 错误时的建议是在每个阶段打印 arr1 和 arr2.... 你能证明一下吗..