在Java中将二叉树展平为数组

Question

我发现这个代码用于在Java中将二叉树展平为数组.我很难理解它是如何工作的.

这是代码:

private static int FlattenTreeIntoArray(Node tree, int[] array, int i)
{
    if (tree == null) return i;
    // Flatten left subtree
    i = FlattenTreeIntoArray(tree.Left, array, i);
    // Get data from the current node
    array[i] = tree.Data;
    // Flatten right subtree
    i = FlattenTreeIntoArray(tree.Right, array, i + 1);
    return i;
} 

我的问题如下:

1. 这是辅助方法,实际调用的方法是什么,或者作为参数(int[] array和int i)传递的是什么？我们不知道二叉树的大小.

2. 该方法如何工作？当它tree是null,它返回i.那是什么意思？

3. 扁平化是如何发生的？为什么i+1被传递给right tree,但i要left tree？

如果您可以使用此二叉树进行演示,则可以很容易地遵循:

Answer 1

除了其他答案之外,我还用这个gif来说明算法的执行情况.您在左侧看到了必须处理的元素,右侧是数组.

Answer 2

这是一个简单的递归示例,一旦您理解了这一点,所有递归树算法都应该开始有意义.我会尽力回答你的问题:

这是辅助方法,如何实际调用实际方法,或者将什么作为参数传递给int i和int []数组 - 我们不知道二叉树的大小

看一下代码,由于这是一个面试类型问题,我们假设int []数组足够大以适应所有内容.

i似乎是要填充的数组的当前索引,因此第一次展平树的调用将设置i为0.

此方法还返回一个整数,该整数是到目前为止已填充的元素数.这意味着最终返回将返回树的全长(以及数组中填充的元素数)

int[] array = new int[size];
Node root = ...
int bytesWritten = FlattenTreeIntoArray(root, array, 0);

//bytesWritten should equal size
assert(bytesWritten == size);

该方法如何起作用:当树为空时,它返回i.那是什么意思？

这假设Node如果没有孩子,则左侧或右侧字段指向null.由于我们i用来维护数组中的位置,如果没有子节点,我们不会更新它的值i.

扁平化是如何发生的？为什么i + 1被传递到右树,但我传给了左树. 通过找到最左边的节点并将其放入来进行展平i.然后找到下一个最左边的节点并将其放入i+1等位置.

让我们来看看你给出的树例子:

node = 8 i = 0; array = {}

得到root的左节点,这是3并递归调用这个flatten方法,当得到1的左节点为null时,得到3的左节点为1,并再次递归调用flatten方法.返回i= 0.现在我们在Node1 array[0] = Node 1's value=`array [0] = 1 的flatten方法中.

现在调用节点1的右侧字段并展平递增i.节点1的右侧字段为空,因此我们返回i的当前值(即1).

现在我们回到节点1的flatten方法并且已经finsished左右递归并且已经到达方法的末尾,所以我们返回当前值为i1.

现在我们回到节点3的flatten方法.我们刚刚完成了为左侧字段调用flatten方法,它返回值1,现在我们设置i.

现在我们用节点3的值更新数组

array[1] = 3;

现在我们用增加的i来展平节点3的右侧字段(节点6) i=2

等等

希望有所帮助