欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode 106. Construct Binary Tree from Inorder and Postorder Traversal

程序员文章站 2022-03-07 23:39:50
...

题目

LeetCode 106. Construct Binary Tree from Inorder and Postorder Traversal

思路

递归构建左子树和右子树

代码

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

class Solution:
    def buildTree(self, inorder, postorder):
        """
        :type inorder: List[int]
        :type postorder: List[int]
        :rtype: TreeNode
        """
        if not postorder: return None
        if len(postorder) == 1:
            return TreeNode(postorder[0])
        index = -1
        for i, v in enumerate(inorder):
            if v == postorder[-1]:
                index = i
                break
        node = TreeNode(postorder[-1])
        if index > 0:
            node.left = self.buildTree(inorder[:index], postorder[:index])
        if index < len(inorder) - 1:
            node.right = self.buildTree(inorder[index + 1:], postorder[index:len(postorder) - 1])
        return node