已知先序和中序怎么求后序

可以使用递归的方法来求解后序遍历。具体步骤如下：

1. 先序遍历的第一个节点为根节点，找到该节点在中序遍历中的位置，将中序遍历分为左子树和右子树两部分。

2. 根据左子树和右子树的节点数，将先序遍历分为左子树和右子树两部分。

3. 对左子树和右子树分别递归求解后序遍历。

4. 将根节点加入后序遍历序列中。

5. 最终得到的序列即为后序遍历序列。

需要注意的是，如果先序遍历和中序遍历序列中有重复的节点，需要特殊处理。

相关问题

已知先序和中序求后序C语言

已知一棵二叉树的前序遍历（Preorder）和中序遍历（Inorder），可以推断出它的后序遍历（Postorder）。这是因为前序、中序和后序遍历分别对应了“根-左-右”、“左-根-右”和“左-右-根”的顺序。

下面是一个简单的算法来实现这个转换：

1. **前序遍历**给出的是根节点 -> 左子树 -> 右子树的顺序。
2. **中序遍历**给出的是左子树 -> 根节点 -> 右子树的顺序。
3. 后序遍历需要将这两个信息组合起来找到根节点的位置。

首先，我们需要从前序遍历中找到根节点。这在前序遍历中是最先出现的元素，因为它代表开始。一旦找到根，我们可以在中序遍历中确定左右子树的位置，因为左子树的节点会出现在根之前，而右子树的节点会出现在根之后。

以下是一个伪代码实现：

void getPostorder(int* preorder, int* inorder, int start, int end) {
   if (start > end)
      return;
   
   // 在中序遍历中找根节点的位置
   int rootIndex = -1;
   for (int i = start; i <= end; ++i) {
       if (inorder[i] == preorder[start]) {
           rootIndex = i;
           break;
       }
   }

   // 后续处理
   int leftEnd = rootIndex - 1; // 在中序中根左边的部分结束位置
   int rightStart = rootIndex + 1; // 在中序中根右边的部分开始位置

   // 递归处理左子树和右子树
   getPostorder(preorder, inorder, start, leftEnd);
   getPostorder(preorder, inorder, rightStart, end);

   // 将根节点添加到结果后
   printf("%d ", preorder[start]);
}

// 调用函数并传入数据
int preorder[] = {1, 2, 4, 5, 3};
int inorder[] = {4, 2, 5, 1, 3};
int n = sizeof(preorder)/sizeof(preorder[0]);
getPostorder(preorder, inorder, 0, n-1);

已知先序中序求后序Java

可以使用递归的方式来实现先序和中序求后序，具体实现代码如下：

public class Tree {
    private static class Node {
        private char value;
        private Node left;
        private Node right;

        public Node(char value) {
            this.value = value;
        }
    }

    public static String preInToPost(String preOrder, String inOrder) {
        if (preOrder == null || inOrder == null || preOrder.length() != inOrder.length()) {
            return null;
        }
        Node root = preInToPost(preOrder.toCharArray(), 0, preOrder.length() - 1, inOrder.toCharArray(), 0, inOrder.length() - 1);
        StringBuilder sb = new StringBuilder();
        postOrder(root, sb);
        return sb.toString();
    }

    private static Node preInToPost(char[] preOrder, int preStart, int preEnd, char[] inOrder, int inStart, int inEnd) {
        if (preStart > preEnd) {
            return null;
        }
        Node root = new Node(preOrder[preStart]);
        int index = findIndex(inOrder, inStart, inEnd, preOrder[preStart]);
        int leftSize = index - inStart;
        root.left = preInToPost(preOrder, preStart + 1, preStart + leftSize, inOrder, inStart, index - 1);
        root.right = preInToPost(preOrder, preStart + leftSize + 1, preEnd, inOrder, index + 1, inEnd);
        return root;
    }

    private static void postOrder(Node root, StringBuilder sb) {
        if (root == null) {
            return;
        }
        postOrder(root.left, sb);
        postOrder(root.right, sb);
        sb.append(root.value);
    }

    private static int findIndex(char[] arr, int start, int end, char target) {
        for (int i = start; i <= end; i++) {
            if (arr[i] == target) {
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        String preOrder = "ABDCEGF";
        String inOrder = "DBAEGCF";
        String postOrder = preInToPost(preOrder, inOrder);
        System.out.println(postOrder); // DCBGEFA
    }
}

该代码中使用了一个内部类 `Node` 表示二叉树的节点，`preInToPost` 方法用于递归构建二叉树，`postOrder` 方法用于递归遍历二叉树并输出后序遍历序列，`findIndex` 方法用于查找中序遍历序列中某个元素的位置。最后在 `main` 方法中调用 `preInToPost` 方法并输出结果。