ruby - 查找二叉树的叶子

正在处理以下问题：

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

我已经打印了左arr和右arr变量的输出，它们看起来很好，我已经测试了我的编织算法。我在概念上离开这里了吗？

最佳答案

我不能评论，所以我会这样做。（记得我不认识鲁比）
我认为双数组（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]]]
我的建议是在每个阶段都打印arr1和arr2。
你能展示一下吗..

关于ruby - 查找二叉树的叶子，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/42428637/