关注上方“深度学习技术前沿”，选择“星标公众号”，
资源干货，第一时间送达！
105. 从前序与中序遍历序列构造二叉树
根据一棵树的前序遍历与中序遍历构造二叉树。
注意:
- 你可以假设树中没有重复的元素。
例如，输入：
前序遍历 preorder = [3,9,20,15,7]中序遍历 inorder = [9,3,15,20,7]
输出：[3,9,20,null,null,15,7]
返回如下的二叉树：
3/ \9 20/ \15 7
前序遍历是根左右，因此preorder第一个元素一定是整个树的根。由于题目说明了没有重复元素，因此我们可以通过preorder[0]去inorder找到根在inorder中的索引pos。
而由于中序遍历是左根右，我们容易找到pos左边的都是左子树，pos右边都是右子树。
Python实现：
# Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = NoneclassSolution:defbuildTree(self, preorder: List[int], inorder: List[int])-> TreeNode:iflen(preorder) == 0:returnNoneeliflen(preorder) == 1:returnTreeNode(preorder[0])else:root = TreeNode(preorder[0])#锁定中序遍历中根节点的位置pos = inorder.index(preorder[0])root.left = self.buildTree(preorder[1:pos+1], inorder[:pos])root.right = self.buildTree(preorder[pos+1:], inorder[pos+1:])returnroot
106. 从中序与后序遍历序列构造二叉树
根据一棵树的中序遍历与后序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如，给出中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树：
3/ \9 20/ \15 7
思路和上题类似：
后序遍历是左右根，因此postorder最后一个元素一定是整个树的根。由于题目说明了没有重复元素，因此我们可以通过postorder[-1]去inorder找到根在inorder中的索引pos。
而由于中序遍历是左根右，我们容易找到pos左边的都是左子树，pos右边都是右子树。
Python代码实现：
# Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = NoneclassSolution:defbuildTree(self, inorder:List[int], postorder:List[int])-> TreeNode:if(len(postorder)==0):returnNoneelif(len(postorder)==1):returnTreeNode(postorder[0])else:root = TreeNode(postorder[-1])pos = inorder.index(postorder[-1])root.left = self.buildTree(inorder[:pos], postorder[:pos])root.right = self.buildTree(inorder[pos+1:], postorder[pos:-1])returnroot
