1

这个问题是关于跟踪递归函数中的递归深度。

int inputArr[]我有一个存储输入值的数组。我创建了一个递归函数，它int inputArr[]根据以下规则将值重新排列为二叉树结构：

  • 每个新的左节点都是通过取左侧的中间值形成的
  • 分别为右节点
  • 如果新子数组中的元素个数是偶数（因此没有中间值），我们从两个中间值中取右边的一个

这已经由我的foo(from: to: ).

我们打印出的值使得n每个节点之前都有空格和一个破折号（n是树的深度）。

我与印刷作斗争。存储深度然后n根据int depthArr[]元素制作空间只会给出错误的输出。

正确的例子：

{1, 2, 3, 4} -> {3, 2, 1, 4}

- 3
 - 2
  - 1
 - 4

{1, 2, 3, 4, 5} -> {3, 2, 1, 5, 4}:

- 3
 - 2
  - 1
 - 5
  - 4

{1, 2, 3, 4, 5, 6, 7, 8} -> {5, 3, 2, 1, 4, 7, 6, 8}

- 5
 - 3
  - 2
   - 1
  - 4
 - 7
  - 6
  - 8

{1, 2, 3, 4, 5, 6} -> {4, 2, 1, 3, 6, 5}

- 4
 - 2
  - 1
  - 3
 - 6
  - 5

我的功能（只关注深度数组，其他一切正常）：

public void foo(int from, int to) {
    outputArr[index] = arr[getIndex(from, to)]; // Just saving the values in correct order
    depthArr[index++] = depth; // Trying out to keep track of current depth

    int prev = to;
    to = getIndex(from, to);

    if (from - to == 0) {
        depth--; // I think that I'm incorrectly decreasing the depth as the recursion goes back
        return;
    }

    depth++;
    foo(from, to - 1);

    if (prev - from != 1)
        foo(to + 1, prev);
}

public int getIndex(int from, int to) { // Get the middle value from, to
    int numOfElements = to - from + 1;
    return from + (numOfElements / 2);
}

WheregetIndex(from: , to: )只会给我从某个索引到某个索引的下一个中间值的索引（输入数组是公共的）。例如：getIndex(0, 2)from {1, 2, 3, 4, 5}is2等。

有没有办法以正确的顺序打印出树，甚至不需要存储深度？还是我忽略了任何简单可靠的方法？

我的输出：

{1, 2, 3, 4, 5}

- 3
 - 2
  - 1
 - 5
  - 4 // Correct



{1, 2, 3, 4, 5, 6, 7, 8}

- 5
 - 3
  - 2
   - 1
  - 4
 - 7
  - 6
 - 8 // Should have one more space

{1, 2, 3, 4, 5, 6, 7}

- 4
 - 2
  - 1
 - 3 // Should have one more space
- 6 // Should have one more space
 - 5
- 7 // Should have one more space
4

1 回答 1

0

解决了。

这int depth是一个静态变量，当从递归返回时会导致问题，因为当左节点完成并且深度已经被减去时，depthArr[]在同一层上跟踪减去的深度。解决方案是通过参数在内部跟踪深度：

    public void foo(int from, int to, int depth) {
    outputArr[index] = arr[getIndex(from, to)];
    depthArr[index++] = depth;

    int prev = to;
    to = getIndex(from, to);

    if (from - to == 0) {
        return;
    }

    foo(from, to - 1, depth + 1); // <-- here

    if (prev - from != 1)
        foo(to + 1, prev, depth + 1); // <-- here
}

现在我们需要调用函数 asfoo(0, inputArr.length, 0)一切都会正常工作。

于 2020-04-11T18:52:42.467 回答