889. 根据前序和后序遍历构造二叉树

Difficulty
Medium
Tags
二叉树
URL
https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/
Star
给定两个整数数组，preorder 和 postorder ，其中 preorder 是一个具有 无重复 值的二叉树的前序遍历，postorder 是同一棵树的后序遍历，重构并返回二叉树。
如果存在多个答案，您可以返回其中 任何 一个。
示例 1：
notion imagenotion image
输入：preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]
输出：[1,2,3,4,5,6,7]
示例 2:
输入: preorder = [1], postorder = [1]
输出: [1]
提示：
  • 1 <= preorder.length <= 30
  • 1 <= preorder[i] <= preorder.length
  • preorder 中所有值都 不同
  • postorder.length == preorder.length
  • 1 <= postorder[i] <= postorder.length
  • postorder 中所有值都 不同
  • 保证 preorder 和 postorder 是同一棵二叉树的前序遍历和后序遍历

法1

思路
对二叉树
notion imagenotion image
有：
notion imagenotion image
题解
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> TreeNode:
        if len(preorder) == 0:
            return None

        if len(preorder) == 1:
            return TreeNode(preorder[0])
        
        cur_val = preorder[0]
        cur_node = TreeNode(cur_val)
				# 此处是根据pre的第2各元素查找的
        idx = postorder.index(preorder[1])
        left_pre = preorder[1:1+idx+1]
        right_pre = preorder[1+idx+1:]

        left_post = postorder[0:idx+1]
        right_post = postorder[idx+1:-1]
        cur_node.left = self.constructFromPrePost(left_pre, left_post)
        cur_node.right = self.constructFromPrePost(right_pre, right_post)
        
        return cur_node