题目描述 假设二叉树中每个结点值为单个字符(不超过100个)，已知其中序序列和后序序列，求二叉树的先序序列。 输入格式 两行，每行一个字符串，分别为二叉树的中序序列和后序序列 输出格式 一个字符串，为二叉树的先序序列

算法思路：

由于后序序列的最后一个元素为树的根节点，因此可以根据后序序列找到根节点，然后再根据中序序列，将树分为左右子树，递归求解即可。

具体来说，假设后序序列的最后一个元素为根节点 $root$，在中序序列中找到 $root$ 的位置 $pos$，则中序序列中 $pos$ 左边的元素为树的左子树，右边的元素为树的右子树。对于左子树和右子树，我们分别递归求解，得到左子树的先序序列 $pre_{left}$ 和右子树的先序序列 $pre_{right}$，然后将 $root$、$pre_{left}$ 以及 $pre_{right}$ 拼接在一起，构成整棵树的先序序列。

递归的结束条件是中序序列为空。

算法时间复杂度为 $O(n^2)$，其中 $n$ 为树的节点数。因为每次递归都需要在中序序列中找到根节点的位置，最坏情况下需要遍历整个中序序列，时间复杂度为 $O(n)$；而总共有 $n$ 个节点需要处理，因此总时间复杂度为 $O(n^2)$。

Python 代码：

相关问题

已知一棵二叉树中每个结点值为单个字符，其中序和后序序列分别为BFDJGACHKEI和FJGDBKHIECA，请画出该二叉树，并给出该二叉树的先序序列

根据中序和后序序列，可以重建该二叉树如下：

      I
     / \
    /   \
   H     E
  / \   / \
 /   \ /   \
B    D K    C
     / \     
    /   \    
   F     G   

该二叉树的先序序列为：`I H B D K F G E C A`

假设二叉树每个结点值为单个字符，采用二叉存储结构存储。设计算法求二叉树中最小的结点值

可以采用中序遍历的方式遍历整棵二叉树，找到最左边的叶子结点即为最小值。具体步骤如下：
1. 从根节点开始，将当前节点入栈。
2. 如果当前节点有左子节点，则将左子节点入栈，直到没有左子节点。
3. 弹出栈顶节点，判断其是否为叶子节点，如果是，则更新最小值。
4. 如果当前节点有右子节点，则将右子节点入栈。
5. 重复步骤2-4，直到栈为空。

代码实现如下：

char findMin(TreeNode* root) {
    stack<TreeNode*> s;
    TreeNode* cur = root;
    char minVal = INT_MAX;
    while (cur != NULL || !s.empty()) {
        while (cur != NULL) {
            s.push(cur);
            cur = cur->left;
        }
        cur = s.top();
        s.pop();
        if (cur->left == NULL && cur->right == NULL) {
            minVal = min(minVal, cur->val);
        }
        cur = cur->right;
    }
    return minVal;
}