如何使用Python实现链表的根据二叉树的中序遍历和后序遍历构建二叉树操作

2023-04-11 00:00:00 二叉树 遍历 如何使用

链表实现二叉树的构建，可以通过递归方式实现。具体步骤如下：

  1. 根据后序遍历，最后一个节点为根节点
  2. 在中序遍历中找到根节点，分成左子树和右子树
  3. 递归构建左子树和右子树，并将根节点和左右子树连接。

下面是Python代码实现：

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

def buildTree(inorder, postorder):
    if not inorder or not postorder:
        return None

    root = TreeNode(postorder[-1])
    idx = inorder.index(root.val)

    root.left = buildTree(inorder[:idx], postorder[:idx])
    root.right = buildTree(inorder[idx+1:], postorder[idx:-1])

    return root

这里我们创建了一个TreeNode类表示二叉树的节点。buildTree函数接收两个参数inorder和postorder，表示中序遍历和后序遍历。首先判断inorder和postorder是否为空，如果为空则返回None。

接下来，我们找到根节点，根据根节点分割成左子树和右子树的中序遍历，同样分割后序遍历。然后递归进行左子树和右子树的构建，最后将根节点和左右子树连接起来。最后返回根节点。

例如，我们有中序遍历["pidancode.com", "编程", "皮蛋"]和后序遍历["pidancode.com", "皮蛋", "编程"]，我们可以通过如下代码构建二叉树：

inorder = ["pidancode.com", "编程", "皮蛋"]
postorder = ["pidancode.com", "皮蛋", "编程"]
root = buildTree(inorder, postorder)

通过递归，我们可以愉快地构建出二叉树了！

相关文章