目录

一、题目

二、示例

三、思路

四、代码

一、题目

根据一棵树的中序遍历与后序遍历构造二叉树。

注意:你可以假设树中没有重复的元素。

二、示例

示例：

中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树：

     3
    /  \
  9   20
      /   \
    15   7

三、思路

中序遍历：左-->根-->右

后序遍历：左-->右-->根

中序遍历+后序遍历 可确定一个独一无二的二叉树

可以根据后序遍历序列中查找根结点，再从中序遍历序列中查找根节点所在的位置，根节点左边部分为左子树，右边部分为右子树。依次类推，依次确定每个结点所在的位置，即可构造出一棵二叉树。

例如，
中序遍历 inorder = [9,3,15,20,7]

后序遍历 postorder = [9,15,7,20,3]

postorder[-1] = 3  3为根结点

因此在inorder数组中，3出现的位置[9,3,15,20,7]，我们用变量n来记录该位置，n = 1

那么我们的树为

         3
       /   \
     9   15 20 7

首先我们先构造左子树，再构造右子树

因此左子树递归传入的数组为inorder[:n]和postorder[:n]

右子树递归传入的数组为inorder[n+1:]和postorder[n:-1]

四、代码

# Definition for a binary tree node.
class TreeNode:def __init__(self, x):self.val = xself.left = Noneself.right = Nonedef __repr__(self):return str(self.val)class Solution:def buildTree(self, inorder, postorder):""":type inorder: List[int]:type postorder: List[int]:rtype: TreeNode"""if len(postorder) == 0:returnroot = TreeNode(postorder[-1])n = inorder.index(root.val)root.left = self.buildTree(inorder[:n], postorder[:n])root.right = self.buildTree(inorder[n + 1:], postorder[n: -1])return rootif __name__ == '__main__':inorder = [9, 3, 15, 20, 7]postorder = [9, 15, 7, 20, 3]s = Solution()root = s.buildTree(inorder, postorder)print(root)