leetcode 重建二叉树

leetcode 重建二叉树

代码:

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        if len(inorder) == 0:
            return None
        root = TreeNode(preorder[0]) # 以第一个先序节点作为根节点
        mid = inorder.index(preorder[0]) # 找到根节点所在中序中的位置,其左边的作为左子树,右边的作为右子树
        #我们在 inorder 中找到 mid 为根节点的下标
        #由于中序遍历特性,mid 左侧都为左子树节点,所以左子树的节点有 mid 个
        #那么同样的,由于前序遍历的特性,preorder 第一个元素(根节点)后跟着的就是它的左子树节点,一共有 mid 个,所以切了 [1:mid+1] 出来
        # 构建左子树
        root.left = self.buildTree(preorder[1:mid+1],inorder[:mid])
        # 构建右子树
        root.right = self.buildTree(preorder[mid+1:],inorder[mid+1:])
        return root

 

上一篇:photoshop鼠绘出拿着红色苹果的帅气美少年


下一篇:【Leetcode】105: 从前序与中序遍历序列构造二叉树