[Leetcode][python]从前序与中序遍历序列构造二叉树/从中序与后序遍历序列构造二叉树
[Leetcode][python]从前序与中序遍历序列构造二叉树/从中序与后序遍历序列构造二叉树
蛮三刀酱
发布于 2019-03-26 17:10:31
发布于 2019-03-26 17:10:31
题目大意
根据二叉树的前序遍历和中序遍历（ 中序和后序）结果生成二叉树 假设没有重复数字
解题思路
参考给中序和后序遍历 看到树首先想到要用递归来解题。以这道题为例：如果一颗二叉树为{1,2,3,4,5,6,7}，则中序遍历为{4,2,5,1,6,3,7}，后序遍历为{4,5,2,6,7,3,1}，我们可以反推回去。由于后序遍历的最后一个节点就是树的根。也就是root=1，然后我们在中序遍历中搜索1，可以看到中序遍历的第四个数是1，也就是root。根据中序遍历的定义，1左边的数{4,2,5}就是左子树的中序遍历，1右边的数{6,3,7}就是右子树的中序遍历。而对于后序遍历来讲，一定是先后序遍历完左子树，再后序遍历完右子树，最后遍历根。于是可以推出：{4,5,2}就是左子树的后序遍历，{6,3,7}就是右子树的后序遍历。而我们已经知道{4,2,5}就是左子树的中序遍历，{6,3,7}就是右子树的中序遍历。再进行递归就可以解决问题了。
前序和中序：
root.left = self.buildTree(preorder[1 : index + 1], inorder[0 : index])
root.right = self.buildTree(preorder[index + 1 : len(preorder)], inorder[index + 1 : len(inorder)])中序和后序：
root.left = self.buildTree(inorder[0 : index], postorder[0 : index])
root.right = self.buildTree(inorder[index + 1 : len(preorder)], postorder[index : len(inorder)-1])代码
前序和中序
class Solution(object):
def buildTree(self, preorder, inorder):
if len(preorder) == 0:
return None
if len(preorder) == 1:
return TreeNode(preorder[0])
root = TreeNode(preorder[0])
index = inorder.index(root.val) # 中序中根节点的位置，左边即为左子树，右边由子树
root.left = self.buildTree(preorder[1 : index + 1], inorder[0 : index])
root.right = self.buildTree(preorder[index + 1 : len(preorder)], inorder[index + 1 : len(inorder)])
return root中序和后序
class Solution(object):
def buildTree(self, inorder, postorder):
if len(inorder) == 0:
return None
if len(inorder) == 1:
return TreeNode(inorder[0])
root = TreeNode(postorder[len(postorder) - 1])
index = inorder.index(postorder[len(postorder) - 1])
root.left = self.buildTree(inorder[ 0 : index ], postorder[ 0 : index ])
root.right = self.buildTree(inorder[ index + 1 : len(inorder) ], postorder[ index : len(postorder) - 1 ])
return root总结
二叉树遍历
- 二叉树的前序、中序、后序遍历（深度优先遍历） 遍历即将树的所有结点都访问且仅访问一次。按照根结点访问次序的不同，可以分为前序遍历，中序遍历，后序遍历。 前序遍历：根结点 -> 左子树 -> 右子树 中序遍历：左子树 -> 根结点 -> 右子树 后序遍历：左子树 -> 右子树 -> 根结点
这里写图片描述
前序遍历：abdefgc 中序遍历：debgfac 后序遍历：edgfbca
- 层次遍历（广度优先遍历） 层次遍历：abcdfeg
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017年07月23日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录