根据前序遍历和中序遍历构建⼆叉树
根据树前序遍历和中序遍历构建⼆叉树
问题：已知⼀个⼆叉树前序遍历为：ABDEGCFH，中序遍历为：DBGEACHF，则该⼆叉树的后序遍历为？
思路是这样的：1：根据前序遍历来确定每次根节点的位置，因为前序遍历先访问的是根节点，所以前序遍历第⼀个位置就是根节点。 2：根据根节点和中序遍历将树划分为左右两棵树。3：根据第⼀步和第⼆步递归的处理左右两棵树。
第⼀步：根据前序遍历 A B D E G C F H 确定头结点是A，根据中序遍历 D B G E A C H F 将树划分为左⼦树 D B G E 和右⼦树 C H F。第⼆步：划分为左右两棵⼦树：对于左⼦树，前序遍历是 B D E G，后续遍历是 D B G E。对于右⼦树，前序遍历是 C F H，后续遍历是 C H F。
第三步：对左⼦树和右⼦树分别运⽤第⼀步和第⼆步进⾏分析。
递归结束的条件：当中序遍历的节点只剩下⼀个节点的时候，那么这个节点就是叶⼦节点。
整体的操作流程如下：
Python代码如下：
class TreeNode:
"""树节点"""
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def reConstructBinaryTree(self, pre, tin):
"""根据前序遍历和中序遍历来重建⼀颗⼆叉树，要求前序遍历和中序遍历当中字符不重复
Args:
pre: 前序遍历  list类型或者者str类型
tin: 中序遍历
Returns：
head: ⼀个TreeNode类型的根节点
"""
build_tree(pre, 0, len(pre)-1, tin, 0, len(tin)-1)
def rebuild_tree(self, pre, pre_start, pre_end, tin, tin_start, tin_end):
"""递归的进⾏树的重建"""
if pre_start > pre_end or tin_start > tin_end:
return None
head = TreeNode(pre[pre_start])
tin_mid = tin.index(pre[pre_start])
left_length = tin_mid - tin_start
head.left = build_tree(pre, pre_start+1, pre_start+left_length,
tin, tin_start, tin_mid-1)
head.right = build_tree(pre,pre_start+left_length+1, pre_end,
tin, tin_mid+1, tin_end)
return head
def post_order_print(head):
"""以后序遍历的⽅式打印⼀颗⼆叉树"""
if head is None:
return
post_order_print(head.left)
post_order_print(head.right)
print(head.val,end='')
if __name__ == '__main__':
pre = 'ABDEGCFH'
tin = 'DBGEACHF'
s = Solution()
head = s.reConstructBinaryTree(pre, tin)
post_order_print(head)  # result: DGEBHFCA
根据树后序遍历和中序遍历构建⼆叉树
道理是⼀样的，根据后序遍历来确定根节点的位置，由于后序遍历最后访问根节点，所以此时最后⼀个节点就是根节点。根据中序遍历来划分左右⼦树，然后迭代求解。
根据树前序遍历和后序遍历不能构建唯⼀的⼆叉树
前序和后序在本质上都是将⽗节点与⼦结点进⾏分离，但并没有指明左⼦树和右⼦树的能⼒，因此得到这两个序列只能明确⽗⼦关系，⽽不能确定⼀个⼆叉树。
二叉树前序中序后序图解
⽐如前序遍历为ABC，后续遍历为CBA，可以构造出下⾯两棵树，可以发现这并不唯⼀：

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。