从前序和中序遍历构造二叉树

[编程题]从前序和中序遍历构造二叉树

热度指数：14081 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给出一棵树的前序遍历和中序遍历，请构造这颗二叉树

注意：

可以假设树中不存在重复的节点

示例1

输入

[1,2],[1,2]

输出

{1,#,2}

示例2

输入

[1,2,3],[2,3,1]

输出

{1,2,#,#,3}

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

Python

牛客986405483号

class Solution:
    def buildTree(self , preorder , inorder ):
        # write code here
        node = None
        if preorder:
            node = TreeNode(preorder[0])
            index = inorder.index(preorder[0])
            node.left = self.buildTree(preorder[1:1 + index], inorder[:index])
            node.right = self.buildTree(preorder[index + 1:], inorder[index + 1:])
        return node

发表于 2021-03-26 11:10:25 回复(0)

Python

wandering_bai

根据前序遍历确定根节点，补一个python解法

class Solution:
    def buildTree(self , preorder , inorder ):
        # write code here
        if not inorder&nbs***bsp;not preorder:
            return None
        root = TreeNode(preorder.pop(0))
        index = inorder.index(root.val)
        root.left = self.buildTree(preorder, inorder[:index])
        root.right = self.buildTree(preorder, inorder[index+1:])
        return root

发表于 2020-06-01 18:32:58 回复(0)