仅提供后序遍历，如何进行二叉树的中序遍历。

Question

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

完全二叉树是一种二叉树，除叶子节点外的每个节点都有两个子节点，并且具有高度为 h 的最后一层树具有 2^h 个叶节点。

你的任务很简单，给出完全二叉树的后序遍历，输出它的中序遍历。

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

格式要求：

输入格式：仅一个字符串，表示后序遍历。

约束条件：1 <= input.length <= 1000

输出格式：输出一个字符串，表示二叉树的中序遍历

示例：

输入样例 0:

BCA

输出样例 0:

BAC

- user11143040

---

首先通过谷歌搜索。 - Eric

我试过了，但是没找到解决方案。如果你有的话，能否分享一下链接？ - user11143040

Answer 1

我本来准备好了完整的回答，但@EricWang已经实施了它。所以这里是一个补充答案，更详细地描述了这个过程。请接受他的回答。

---

我将使用后序遍历DEBFGCA，因为考虑到更多的节点会更有用。

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

更一般地，我们知道左子树的后序遍历是字符0到(tree.length - 1)/2 - 1，右子树的后序遍历是字符(tree.length - 1)/2 - 1到tree.length - 2。节点是最后一个字符，在tree.length - 1处。

显然，要将其更改为中序遍历，我们只需要确定左子树和右子树，将它们更改为中序遍历，然后返回 LLLNRRR。我们可以使用递归将左右子树转换为中序遍历。

例如，从 DEBFGCA 开始。我们知道结构是 LLLRRRN，所以左子树是 DEB，右子树是 FGC，节点是 A。我们想将 DEB 转换为中序遍历...

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

处理 FGC。与之前相同，返回 FCG。

现在我们知道中序遍历的左子树是DBE，右子树是FCG。返回LLLNRRR，即DBEAFCG。

- canton7

---

非常感谢您。 - user11143040

Answer 2

你可以使用递归来动态地完成它。

---

机制

• 将一棵树分成3部分：left、right和root。
• 按顺序重新连接它们：left、root、right。
• 递归地分裂，直到子树的长度为1。

---

代码 - 用Java

PostToInOrder.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;
    }
}

"PostToInOrderTest.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是一棵完全二叉树，但不是完美二叉树。

- Eric