首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

如何从preorder和inorder遍历构建二叉树

从preorder和inorder遍历构建二叉树是一个常见的编程问题。以下是一个使用Python实现的解决方案:

代码语言:python
代码运行次数:0
复制
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_index = inorder.index(root_val)
    left_inorder = inorder[:root_index]
    right_inorder = inorder[root_index+1:]
    left_preorder = preorder[1:1+len(left_inorder)]
    right_preorder = preorder[1+len(left_inorder):]
    left_tree = buildTree(left_preorder, left_inorder)
    right_tree = buildTree(right_preorder, right_inorder)
    return TreeNode(root_val, left_tree, right_tree)

这个解决方案首先定义了一个TreeNode类,用于表示二叉树的节点。然后,定义了一个buildTree函数,该函数接受两个列表作为参数:preorderinorderpreorder列表表示前序遍历,inorder列表表示中序遍历。

函数首先检查preorderinorder列表是否为空,如果为空,则返回None。接下来,根据preorder列表的第一个元素(即根节点的值)找到inorder列表中的根节点位置。然后,将inorder列表分为左子树和右子树的列表,以及preorder列表分为左子树和右子树的前序遍历列表。

接下来,递归地调用buildTree函数,分别使用左子树的前序遍历和中序遍历列表以及右子树的前序遍历和中序遍历列表来构建左子树和右子树。最后,返回一个新的TreeNode实例,其中包含根节点的值、左子树和右子树。

这个解决方案的时间复杂度为O(n),其中n是二叉树中节点的数量。

页面内容是否对你有帮助?
有帮助
没帮助

相关·内容

没有搜到相关的视频

领券