已知一棵二叉树的先序遍历序列和中序遍历序列分别为1 2 4 5 3 6 和 4 2 5 1 3 6 ，画出这颗二叉树并求其后序序列。

首先根据先序遍历的第一个节点确定根节点，即为1。然后在中序遍历中找到1的位置，可以将中序遍历分为左子树和右子树两部分。左子树的中序遍历为4 2 5，右子树的中序遍历为3 6。

接下来考虑左子树和右子树的先序遍历序列。左子树的先序遍历为2 4 5，右子树的先序遍历为3 6。

对于左子树，其先序遍历的第一个节点为2，因此2为左子树的根节点。根据同样的方法继续划分左右子树，可以得到左子树的先序遍历为4 5，中序遍历为4 2 5；右子树的先序遍历为无，中序遍历为3 6。

对于左子树的左子树，其先序遍历的第一个节点为4，因此4为左子树的左子树的根节点。由于该节点没有左右子树，因此得到左子树的左子树的后序遍历为4。

对于左子树的右子树，其先序遍历的第一个节点为5，因此5为左子树的右子树的根节点。同样地，由于该节点没有左右子树，得到左子树的右子树的后序遍历为5。

对于右子树，其先序遍历的第一个节点为3，因此3为右子树的根节点。由于该节点没有左子树，右子树的后序遍历为6 3。

综上所述，该二叉树的后序遍历为4 5 2 6 3 1。

二叉树的图示如下：

        1
       / \
      2   3
     / \   \
    4   5   6

相关问题

已知二叉树的先序遍历序列和中序遍历序列，输出其后序遍历序列和层次序遍历序列

可以通过先序遍历序列和中序遍历序列重建二叉树，然后对重建后的二叉树进行后序遍历和层次遍历即可。

具体步骤如下：

1. 根据先序遍历序列确定根结点。

2. 在中序遍历序列中找到根结点所在位置，根结点左边的序列是左子树的中序遍历序列，右边的序列是右子树的中序遍历序列。

3. 通过左子树的中序遍历序列长度确定先序遍历序列中左子树的先序遍历序列，右子树的先序遍历序列为剩余部分。

4. 递归处理左子树和右子树，重建二叉树。

5. 对重建后的二叉树进行后序遍历和层次遍历。

下面是 Python 代码实现：

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

def buildTree(preorder, inorder):
    if not preorder or not inorder:
        return None
    root = TreeNode(preorder[0])
    inorderIndex = inorder.index(preorder[0])
    leftInorder = inorder[:inorderIndex]
    rightInorder = inorder[inorderIndex+1:]
    leftPreorder = preorder[1:len(leftInorder)+1]
    rightPreorder = preorder[len(leftInorder)+1:]
    root.left = buildTree(leftPreorder, leftInorder)
    root.right = buildTree(rightPreorder, rightInorder)
    return root

def postorderTraversal(root):
    if not root:
        return []
    stack = [root]
    res = []
    while stack:
        node = stack.pop()
        res.append(node.val)
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    return res[::-1]

def levelOrder(root):
    if not root:
        return []
    queue = [root]
    res = []
    while queue:
        level = []
        for i in range(len(queue)):
            node = queue.pop(0)
            level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        res.append(level)
    return res

preorder = [1, 2, 4, 5, 3, 6, 7]
inorder = [4, 2, 5, 1, 6, 3, 7]
root = buildTree(preorder, inorder)
print(postorderTraversal(root)) # 输出后序遍历序列 [4, 5, 2, 6, 7, 3, 1]
print(levelOrder(root)) # 输出层次遍历序列 [[1], [2, 3], [4, 5, 6, 7]]

已知先序遍历序列和中序遍历序列建立二叉树

### 回答1：
已知先序遍历序列和中序遍历序列，可以建立一棵二叉树。具体建立方法如下：

1. 先序遍历序列的第一个元素为根节点，将其在中序遍历序列中找到，可以将中序遍历序列分成左子树和右子树两部分。

2. 根据左子树和右子树的元素个数，可以将先序遍历序列分成左子树和右子树两部分。

3. 对左子树和右子树分别递归建立二叉树。

4. 将左子树和右子树作为根节点的左右子树，连接到根节点上。

5. 递归结束后，得到完整的二叉树。

需要注意的是，如果先序遍历序列和中序遍历序列中有重复元素，需要根据先序遍历序列的顺序来确定左右子树的位置。

### 回答2：
在已知一个二叉树的先序遍历序列和中序遍历序列的情况下，我们可以通过这两个序列来重建这个二叉树。

首先，我们需要知道先序遍历和中序遍历的定义和特点：

- 先序遍历：先遍历当前节点，再遍历左子树，最后遍历右子树；
- 中序遍历：先遍历左子树，再遍历当前节点，最后遍历右子树。

根据先序遍历的特点，我们可以知道先序遍历的第一个元素必然是根节点，而根据中序遍历的特点，我们可以知道根节点在中序遍历中所处的位置是左子树的所有节点后面。因此，我们可以用先序遍历的第一个元素找到根节点，并在中序遍历中将左子树的所有节点和右子树的所有节点划分出来。

接下来，我们通过递归处理左子树和右子树，可以将整个二叉树重建出来。重建二叉树的方法是：

1. 针对先序遍历和中序遍历的左子序列，建立其对应的左子树；
2. 针对先序遍历和中序遍历的右子序列，建立其对应的右子树。

因此，我们可以写出递归构建二叉树的伪代码：

buildTree(preorder, inorder):
    if preorder is empty:
        return null

    root = TreeNode(preorder[0])
    idx = inorder.index(preorder[0])
    
    left_preorder = preorder[1:idx+1]
    left_inorder = inorder[:idx]

    right_preorder = preorder[idx+1:]
    right_inorder = inorder[idx+1:]

    root.left = buildTree(left_preorder, left_inorder)
    root.right = buildTree(right_preorder, right_inorder)

    return root

时间复杂度为 $O(n^2)$，主要是每次都要在中序遍历中查找根节点的位置。优化时间复杂度的方法是，可以使用一个哈希表来记录中序遍历中每个节点的位置，可以将查找根节点的位置的时间复杂度降为 $O(1)$。因此，时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。

### 回答3：
二叉树是一种常见的数据结构，它由一些节点和连接这些节点的边组成。其中，每个节点至多有两个子节点。如果一个节点没有子节点，则称其为叶节点。底部的节点是深度为1的节点，除非它是根节点，否则它的深度为它父节点的深度加1。在二叉树中，有两种遍历方式，分别是深度优先遍历和广度优先遍历。

对于已知先序遍历序列和中序遍历序列建立二叉树，首先需要明确什么是先序遍历和中序遍历。先序遍历是指先遍历根节点，然后遍历左子树和右子树；中序遍历是指先遍历左子树，然后遍历根节点，最后遍历右子树。因此，通过先序遍历和中序遍历，我们可以唯一地确定一个二叉树。

具体建立二叉树的步骤如下：

1. 首先，根据先序遍历序列，确定根节点。

2. 然后，在中序遍历序列中查找根节点的位置，根节点左侧的序列为左子树的中序遍历序列，右侧的序列为右子树的中序遍历序列。

3. 根据左子树的中序遍历序列和右子树的中序遍历序列，可以得到左子树的先序遍历序列和右子树的先序遍历序列。左子树的先序遍历序列的第一个节点为其根节点，右子树的先序遍历序列的第一个节点为其根节点。

4. 重复以上步骤，递归建立左右子树。

需要注意的是，如果先序遍历序列和中序遍历序列中含有重复节点，必须先建立左子树，再建立右子树。

总之，通过已知先序遍历序列和中序遍历序列建立二叉树需要根据根节点的位置将序列分成左右子树的中序遍历序列，并通过递归的方式逐步建立左右子树。这一过程需要仔细地分析，同时注意处理好重复节点的情况。