从中序与后序遍历序列构造二叉树

以下是根据中序遍历和后序遍历序列构造二叉树的方法：

一、基本思路

1. 后序遍历序列的最后一个元素为根节点的值。
2. 在中序遍历序列中找到根节点的值，其左边的元素为左子树的中序遍历序列，右边的元素为右子树的中序遍历序列。
3. 根据左子树和右子树的节点数量，可以确定后序遍历序列中左子树和右子树的部分。
4. 递归地构建左子树和右子树。

二、示例分析

例如，中序遍历序列为[9,3,15,20,7]，后序遍历序列为[9,15,7,20,3]。

1. 首先，后序遍历序列的最后一个元素3是根节点的值。
2. 在中序遍历序列中找到3，其左边的[9]是左子树的中序遍历序列，右边的[15,20,7]是右子树的中序遍历序列。
3. 后序遍历序列中，除去根节点3，[9]对应左子树的后序遍历序列，[15,7,20]对应右子树的后序遍历序列。
4. 对于左子树，中序遍历序列为[9]，后序遍历序列为[9]，可以构建出左子树只有一个节点9。
5. 对于右子树，中序遍历序列为[15,20,7]，后序遍历序列为[15,7,20]，重复上述步骤，以20为根节点，左子树为15，右子树为7。

三、代码实现（以 Python 为例）

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
def buildTree(inorder, postorder):
    if not inorder or not postorder:
        return None
    root_val = postorder[-1]
    root = TreeNode(root_val)
    index = inorder.index(root_val)
    left_inorder = inorder[:index]
    right_inorder = inorder[index + 1:]
    left_postorder = postorder[:index]
    right_postorder = postorder[index:-1]
    root.left = buildTree(left_inorder, left_postorder)
    root.right = buildTree(right_inorder, right_postorder)
    return root

你可以使用以下方式调用这个函数：

inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]
root = buildTree(inorder, postorder)

四、时间和空间复杂度

• 时间复杂度：对于节点数为 的二叉树，由于每次递归都要在中序遍历序列中查找根节点的位置，因此时间复杂度为 。可以通过使用哈希表存储中序遍历序列中节点值到索引的映射来优化查找过程，优化后时间复杂度为 。
• 空间复杂度：取决于递归调用的栈空间，最坏情况下为 。