如何使用堆栈安全（基于堆）递归将二叉树转换为 java 中的列表？

Question

问题是：如何使用尾递归实现下面的方法 (toListPreOrderLeft)？

 public List<A> toListPreOrderLeft() {
        return toListPreOrderLeft_(this, list()).eval();
    }

    private TailCall<List<A>> toListPreOrderLeft_(TreeNode<A> tree, List<A> list) {
        return ???
    }

详情：

假设我有这棵树：

使用 pre-order-left 算法将其转换为列表将生成列表：[4,2,1,3,6,5,7]

我可以在树中使用堆栈递归来实现这个算法 class:

 public List<A> toListPreOrderLeft() {
            return list(this.value)
                    .concat(this.left.toListPreOrderLeft())
                    .concat(this.right.toListPreOrderLeft());
        }

其中 concat 只是连接两个列表，而 this 指的是我在其上调用该方法的树节点。
（我正在使用我自定义的 List 和 Tree 实现）。

但是 如果我按以下顺序插入树，此实现将溢出堆栈：100000,99999,99998,99997,...,3,2,1。

这是我用来表示尾递归调用的class：

public abstract class TailCall<T> {

    public abstract TailCall<T> nextCall();

    public abstract T eval();

    public abstract boolean isIntermediate();

    //this constructor is to prevent this class from being extended by other classes
    private TailCall() {
    }

    public static <T> TailCall<T> terminalCall(T t) {
        return new TerminalCall<>(t);
    }

    public static <T> TailCall<T> intermediateCall(Supplier<TailCall<T>> nextCall) {
        return new IntermediateCall<>(nextCall);
    }

    private static class TerminalCall<T> extends TailCall<T> {
        private final T t;

        private TerminalCall(T t) {
            this.t = t;
        }

        @Override
        public T eval() {
            return t;
        }

        @Override
        public TailCall<T> nextCall() {
            throw new IllegalStateException("Terminal has no next call");
        }

        @Override
        public boolean isIntermediate() {
            return false;
        }
    }

    private static class IntermediateCall<T> extends TailCall<T> {
        private final Supplier<TailCall<T>> nextCall;

        private IntermediateCall(Supplier<TailCall<T>> nextCall) {
            this.nextCall = nextCall;
        }

        @Override
        public T eval() {
            TailCall<T> tailCall = this;
            while (tailCall.isIntermediate()) {
                tailCall = tailCall.nextCall();
            }
            return tailCall.eval();
        }

        @Override
        public TailCall<T> nextCall() {
            return nextCall.get();
        }

        @Override
        public boolean isIntermediate() {
            return true;
        }
    }
}

下面是一个示例，说明如何使用中序遍历和尾递归实现将树转换为列表的方法 class（我们不断旋转树，直到它变成这样有序链表):

   public List<A> toListInOrderLeft() {
        return toListInOrderLeft_(this, list()).eval();
    }

    private TailCall<List<A>> toListInOrderLeft_(TreeNode<A> tree, List<A> accumulator) {
        return tree.isEmpty()
                ? TailCall.terminalCall(accumulator)
                : tree.right().isEmpty()
                ? intermediateCall(() -> toListInOrderLeft_(tree.left(), accumulator.prepend(tree.value()))) //prepend adds value at the start of a list
                : intermediateCall(() -> toListInOrderLeft_(tree.rotateLeft(), accumulator));
    }

这里对问题中的代码做一个简单的解释：

• TailCall 是一个 class 表示递归调用，因此我们创建一个 [=18= 的实例，而不是通过推送新堆栈帧来进行递归调用] 可以是中间或终端 subclass 取决于递归调用是最后一次调用还是使用供应商（实现惰性）嵌入其中的下一个调用（在 TailCall 对象中）评估）。所以在任何时间点，我们要么有 1 个 referenced 对象代表整个递归链，要么最多有 2 个 referenced 对象代表它（和这个后一种情况发生在我们开始使用 eval 方法

  评估 TailCall 的下一次调用时

• 说了这么多，很容易看出示例方法 toListInOrderLeft 是如何工作的，它调用了一个 return 是 TailCall 的辅助方法（表示第一个递归调用），然后在这个 returned 对象上调用 eval 来计算递归调用直到结束。至于 helper 方法，它需要一个 accumulator（最初是一个空列表）并开始向它附加从树节点获取的值。当达到终止条件时，我们 return 这个累加器包装在辅助方法的终止调用中。

Answer 1

TailCall 不能真正用作堆栈来记住东西。可以对尾递归进行建模，但是toListPreorderLeft的递归实现不只是尾递归。

许多语言都提供类似于 TailCall 的“单子”类，但具有类似 TailCall.then(...) 的方法，您可以使用这些方法将内容链接在一起。如果没有此功能，您将需要创建另一个堆栈——显式或隐式。

你的 toListInorderLeft 方法有同样的问题，但你通过改变树来作弊，有效地使用树作为你的堆栈。这个技巧对预购不起作用。

你可以通过将递归算法转化为“连续传递方式”来解决这个问题。这隐式地生成了一堆 lambda 函数：

class TreeNode<A> {
    
    TreeNode<A> left;
    TreeNode<A> right;
    A value;

    ...

    public TailCall<List<A>> toListPreOrderLeft() {
        return _toListPreOrderLeft(new ArrayList<>(), null);
    }

    private TailCall<List<A>> _toListPreOrderLeft(List<A> accumulator, Function<List<A>, TailCall<List<A>>> continuation) {
        accumulator.add(this.value);
        if (this.left != null && this.right != null) {
            final Function<List<A>, TailCall<List<A>>> cont2 = (accum) ->
                    this.right._toListPreOrderLeft(accum, continuation);
            return TailCall.intermediateCall(() -> this.left._toListPreOrderLeft(accumulator, cont2));
        } else if (this.right != null) {
            return TailCall.intermediateCall(() -> this.right._toListPreOrderLeft(accumulator, continuation));
        } else if (this.left != null) {
            return TailCall.intermediateCall(() -> this.right._toListPreOrderLeft(accumulator, continuation));
        } else if (continuation != null) {
            return TailCall.intermediateCall(() -> continuation.apply(accumulator));
        }
        return TailCall.terminalCall(accumulator);
    }
}

continuation参数捕获的是当前调用结束后还有待完成的工作。从 cont2 到 continuation 的链接形成一个隐式堆栈。

请注意，这是避免堆栈溢出的可怕方法。理解算法并像这样编写一个很好的迭代实现要好得多：

    public List<A> toListPreOrderLeft() {
        final List<A> accumulator = new ArrayList<>();
        final List<TreeNode<A>> treeStack = new ArrayList<>();
        TreeNode<A> n = this;
        for (;;) {
            accumulator.add(n.value);
            if (n.left != null) {
                if (n.right != null) {
                    treeStack.add((n.right));
                }
                n = n.left;
            } else if (n.right != null) {
                n = n.right;
            } else if (!treeStack.isEmpty()) {
                n = treeStack.remove(treeStack.size()-1);
            } else {
                break;
            }
        }
        return accumulator;
    }