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

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

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

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

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

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

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

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

相关问题

已知先序中序求后序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` 方法并输出结果。

已知二叉树求先序中序后序

假设我们已知一棵二叉树的先序遍历序列和中序遍历序列，可以通过以下步骤来求出它的后序遍历序列：

1. 在先序序列中，第一个元素为根节点。
2. 在中序序列中，找到根节点的位置，根节点左侧的部分为左子树的中序遍历序列，右侧的部分为右子树的中序遍历序列。
3. 根据左子树的中序遍历序列的长度，可以在先序遍历序列中确定左子树的先序遍历序列和右子树的先序遍历序列。
4. 递归地对左子树和右子树重复以上步骤，直到子树为空或只有一个节点。
5. 最后将根节点加入后序遍历序列中，即可得到二叉树的后序遍历序列。

下面是一个 Python 代码示例：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def buildTree(preorder, inorder):
    if not preorder or not inorder:
        return None
    root_val = preorder[0]
    root = TreeNode(root_val)
    idx = inorder.index(root_val)
    left_inorder = inorder[:idx]
    right_inorder = inorder[idx+1:]
    left_preorder = preorder[1:1+len(left_inorder)]
    right_preorder = preorder[1+len(left_inorder):]
    root.left = buildTree(left_preorder, left_inorder)
    root.right = buildTree(right_preorder, right_inorder)
    return root

def postorderTraversal(root):
    if not root:
        return []
    res = []
    res.extend(postorderTraversal(root.left))
    res.extend(postorderTraversal(root.right))
    res.append(root.val)
    return res

preorder = [1, 2, 4, 5, 3, 6, 7]
inorder = [4, 2, 5, 1, 6, 3, 7]
root = buildTree(preorder, inorder)
postorder = postorderTraversal(root)
print(postorder)  # 输出 [4, 5, 2, 6, 7, 3, 1]

以上代码中，`buildTree` 函数接收先序遍历序列和中序遍历序列作为参数，返回构建出的二叉树的根节点。`postorderTraversal` 函数接收根节点作为参数，返回后序遍历序列。在 `buildTree` 函数中，我们先根据先序序列中的第一个元素构建出根节点，然后在中序序列中找到根节点的位置，根据位置将中序序列分为左右两部分，递归地构建出左右子树。在 `postorderTraversal` 函数中，我们先递归遍历左子树和右子树，然后将根节点的值加入到后序序列中。