在 Java 中打印二叉树

Question

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

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

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

我的 foo(from: to: ).

已经解决了这个问题

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

我在印刷方面遇到了困难。存储深度然后根据 int depthArr[] 元素创建 n 空间只会给出错误的输出。

正确的例子：

{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);
}

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

有没有办法在不需要存储深度的情况下以正确的顺序打印出树？或者有什么我忽略的简单可靠的方法吗？

我的输出：

{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

Answer 1

已解决。

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
}

现在我们需要将函数调用为 foo(0, inputArr.length, 0)，一切都会正常。

在 Java 中打印二叉树

Printing out binary tree in Java

java

binary-tree