一、根据前序与中序构造二叉树
- 前序遍历：确定根节点root，最左端的节点即为根节点
- 中序遍历：确定根节点左右两边的节点，通过计算左右两边节点集合的大小
- 对root左节点集合与右节点集合执行重复操作，不断确定小集合的根节点，最终可构造出一整棵二叉树
- 树的存储可以采用定义类或结构体，这里为方便存储，采用哈希表left存储左节点，right存储右节点
from collections import Counter
in_order = [1,2,3,4,5,6,7]
pre_order = [4,1,3,2,6,5,7]
idx = Counter()
for i, x in enumerate(in_order):
idx[x] = i
left, right = Counter(), Counter()
def dfs(l1: int, r1: int, l2: int, r2: int) -> int:
if l1 > r1:
return 0
root = pre_order[l2]
id = idx[root]
left[root] = dfs(l1, id - 1, l2 + 1, l2 + (id - l1))
right[root] = dfs(id + 1, r1, l2 + (id - l1) + 1, r2)
return root
root = dfs(0, n - 1, 0, n - 1)
二、根据后序与中序构造二叉树
其方法同上
from collections import Counter
in_order = [1,2,3,4,5,6,7]
post_order = [2,3,1,5,7,6,4]
idx = Counter()
for i, x in enumerate(in_order):
idx[x] = i
left, right = Counter(), Counter()
def dfs(l1: int, r1: int, l2: int, r2: int) -> int:
if l1 > r1:
return 0
root = post_order[r2]
id = idx[root]
left[root] = dfs(l1, id - 1, l2, l2 + (id - l1) - 1)
right[root] = dfs(id + 1, r1, l2 + (id - l1), r2 - 1)
return root
root = dfs(0, n - 1, 0, n - 1)
三、根据层序与中序构造二叉树
- 根据层序遍历的性质，层序数组中的第一个元素一定是根节点root（在中序数组中的下标为idx）
- 找到root，再结合中序数组，就可以找到，根节点的左儿子集合与右儿子集合
- 找到在左儿子集合(l,idx - 1)中出现且按照层序数组中的顺序出现的序列，其序列中的第一个元素就是下一个根节点
- 右儿子集合(idx + 1,r)同理
from collections import Counter
level_order = [4, 1, 6, 3, 5, 7, 2]
in_order = [1, 2, 3, 4, 5, 6, 7]
n = len(in_order)
mp = Counter()
for i, x in enumerate(in_order):
mp[x] = i
left, right = Counter(), Counter()
def dfs(l, r):
if l > r:
return 0
root = 0
for x in level_order:
if l <= mp[x] <= r:
root = x
break
idx = mp[root]
left[root] = dfs(l, idx - 1)
right[root] = dfs(idx + 1, r)
return root
def pre_order(root):
if root:
print(root, end=' ')
pre_order(left[root])
pre_order(right[root])
root = dfs(0,n - 1)
pre_order(root) # 4 1 3 2 6 5 7
四、根据前序与后序构造二叉树
-
前序与后序可以判别根节点，但去无法判别左子树与右子树
-
因此，如果只根据前序与后序是无法构造出唯一的二叉树的（除非所有的非叶子节点都有两个儿子，这样就不会混淆）
-
举例
既然不可以唯一构造，那我们构造出其中 一种 即可！
方案一：
from collections import Counter
#
pre_order = [4,1,3,2,6,5,7]
post_order = [2,3,1,5,7,6,4]
# pre_order = [1,2,4,5,3,6,7]
# post_order = [4,5,2,6,7,3,1]
n = len(pre_order)
left, right = Counter(), Counter()
def dfs(a,b):
if not a:
return 0
root = a[0]
if len(a) == 1:
return root
idx = b.index(a[1])
left[root] = dfs(a[1:idx + 2],b[:idx + 1])
right[root] = dfs(a[idx + 2:],b[idx + 1:-1])
return root
def in_order(root):
if root:
in_order(left[root])
print(root, end=' ')
in_order(right[root])
print(dfs(pre_order,post_order))
in_order(dfs(pre_order,post_order))
方案二
from collections import Counter
pre_order = [4,1,3,2,6,5,7]
post_order = [2,3,1,5,7,6,4]
n = len(pre_order)
mp = Counter()
for i, x in enumerate(post_order):
mp[x] = i
left, right = Counter(), Counter()
def dfs(l1, r1,l2,r2):
if l1 > r1:
return 0
root = pre_order[l1]
if l1 == r1:
return root
idx = mp[pre_order[l1 + 1]]
left[root] = dfs(l1 + 1,l1 + 1 + idx - l2,l2,idx)
right[root] = dfs(l1 + 1 + idx - l2 + 1,r1,idx + 1,r2 - 1)
return root
def in_order(root):
if root:
in_order(left[root])
print(root, end=' ')
in_order(right[root])
print(dfs(0,n - 1,0,n - 1))
in_order(dfs(0, n - 1,0,n - 1))
拓展
已知二叉树的前序遍历与后序遍历，求可以构造的二叉树的种类数？【确认根节点后，枚举左儿子节点集合长度！】
pre_order = [4,1,3,2,6,5,7]
post_order = [2,3,1,5,7,6,4]
n = len(pre_order)
def dfs(l1,r1,l2,r2):
if l1 > r1:
return 1
if pre_order[l1] != post_order[r2]:
return 0
cnt = 0
for i in range(l1,r1 + 1):
left_cnt = dfs(l1 + 1,i,l2,l2 + i - l1 - 1)
right_cnt = dfs(i + 1,r1,l2 + i - l1 - 1 + 1,r2 - 1)
if left_cnt > 0 and right_cnt > 0:
cnt += left_cnt * right_cnt
return cnt
print(dfs(0,n - 1,0,n - 1))