二叉树从只提供后序遍历到有序遍历

Question

我在编码挑战中遇到了一个问题。

完整二叉树是一种二叉树，其中除叶节点外的每个节点都有两个子节点，且树的最后一级边高度h有2^h叶节点。

您的任务很简单，给定完整二叉树的后序遍历，请按顺序遍历打印其。

二叉树中的元素为字符类型，即每个节点存储一个字符值。

输入/输出格式

输入格式：

只有一个字符串输入表示后序遍历。

限制条件：

1.

输出格式：

输出一个表示二叉树按顺序遍历的字符串

样品

样本输入0：

BCA

示例输出0：

美国银行




Answer 1

您可以使用递归动态地执行此操作。

• 将树分成3部分：左边，右边，root。
• 按顺序重新连接它们：左边，root，右边。
• 递归拆分，直到子树的长度为1。

波斯托诺德。JAVA

public class PostToInOrder {
    public static String convert(String post) {
        checkPerfect(post); // check whether tree is perfect,

        return convertInner(post);
    }

    private static String convertInner(String post) {
        int len = post.length();
        if (len == 1) return post; // base case,

        String left = post.substring(0, len >> 1); // left of post,
        String right = post.substring(len >> 1, len - 1); // right of post,
        char root = post.charAt(len - 1); // root of post,

        return convertInner(left) + root + convertInner(right);
    }

    private static void checkPerfect(String tree) {
        if (!isPerfect(tree)) throw new IllegalArgumentException("input is not perfect tree, size: " + tree.length());
    }

    private static boolean isPerfect(String tree) {
        int len = tree.length();
        if (len < 1) return false;

        while (len != 0) {
            if ((len & 1) == 0) return false;
            len >>= 1;
        }

        return true;
    }
}

波斯托诺德测试。java:
（单元测试，通过TestNG）

import org.testng.Assert;
import org.testng.annotations.Test;

public class PostToInOrderTest {
    @Test
    public void test() {
        Assert.assertEquals(PostToInOrder.convert("BCA"), "BAC");
        Assert.assertEquals(PostToInOrder.convert("02146538A9CEDB7"), "0123456789ABCDE");

        Assert.assertEquals(PostToInOrder.convert("A"), "A"); // single element,
    }

    @Test(expectedExceptions = IllegalArgumentException.class)
    public void test_invalid_empty() {
        PostToInOrder.convert("");
    }

    @Test(expectedExceptions = IllegalArgumentException.class)
    public void test_invalid_notPerfect() {
        PostToInOrder.convert("AB");
    }
}

顺便说一句：

• 所述的树是一个完美二叉树<它是完全二叉树的一个子类型<一棵完整的树不一定是完美的，它的最后一层可能缺少一些叶子
  例如AB是一棵完整的树，但不是完美的树

Answer 2

我确实准备好了一个完整的答案，但是@EricWang在实现上击败了我。下面是一个补充答案，更详细地描述了这个过程。请接受他的回答。

我将使用后序遍历<代码> DEFFGCA，因为考虑稍微多的节点是有用的。

因为树是完整的，对于任何给定的节点，我们都知道左边的子节点数与右边的子节点数相同。因此，我们可以查看后序遍历DEBFGCA，知道它具有结构lllrrn，其中L是左子树的后序遍历，R是右子树的后序遍历，N是节点本身。

更一般地，我们知道左边子树的后序遍历是字符0到（tree.length-1）/2-1，右边子树的后序遍历是字符（tree.length-1）/2-1到tree.length-2。节点是最后一个字符，位于tree.length-1。

显然，要将其更改为顺序遍历，我们只需识别左、右子树，将其更改为顺序遍历，然后返回LLLNRRR。我们可以使用递归将左右子树按顺序转换为。

例如，从DEBFGCA开始。我们知道结构是lllrrn，因此左子树是DEB，右子树是FGC，节点是A。我们要将DEB转换为以便。。。

处理DEB。我们知道左边的子树是D，右边是E，节点是B。两个子树的长度都是1，叶子也是。不需要进一步的递归。返回LNR，即DBE。

过程FGC。与前面一样，返回FCG。

现在我们知道按顺序排列的左边是DBE，右边是FCG。返回LLLNRRR，即DBEAFCG。