# 889.construct binary tree from preorder and postorder traversal

## Description

Return any binary tree that matches the given preorder and postorder traversals.

Values in the traversals pre and post are distinct positive integers.

### Example 1:

``````Input: pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1]

Output: [1,2,3,4,5,6,7]
``````

### Note:

• 1 <= pre.length == post.length <= 30
• pre[] and post[] are both permutations of 1, 2, …, pre.length.
• It is guaranteed an answer exists. If there exists multiple answers, you can return any of them.

## 分析

1. 根据先序遍历pre和后续遍历post构建二叉树，常规递归方法；
2. 递归的结束条件是：pre长度为0返回None，长度为1，返回TreeNode(pre[0])
3. pre[0]作为当前过程的根节点，pre[1:indexof(pre[1])+2]作为左子树先序，post[:indexof(pre[1])+1]作为左子树后序，pre[indexof(pre[1])+2:]作为右子树先序，post[indexof(pre[1])+1：-1]作为右子树后序；
4. 如例：{[2,4,5],[4,5,2]}为左子树，{[3，6，7],[6,7,3]}为右子树，indexof(pre[1])为pre[1] (2)在post中的位置，为：2
5. 以此类推

## 参考代码

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

class Solution:
def constructFromPrePost(self, pre, post):
if(len(pre)==0):
return None
if(len(pre)==1):
return TreeNode(pre[0])