1497. 树的遍历
摘要
Title: 1497. 树的遍历
Tag: 二叉树、中序遍历、后序遍历
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
1497. 树的遍历
-
题意
一个二叉树，树中每个节点的权值互不相同。
现在给出它的后序遍历和中序遍历，请你输出它的层序遍历。 -
思路
抓住两点：
- 中序遍历里面，先找到根节点的位置，左子树在根左边，右子树在根右边
- 后序遍历里面，最后一个点，一定是根节点
首先先去用哈希表存中序遍历里每个值的下标是多少
-
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47'''
Author: NEFU AB-IN
Date: 2022-04-18 22:30:26
FilePath: \ACM\Acwing\1497.py
LastEditTime: 2022-04-18 22:32:52
'''
import sys
sys.setrecursionlimit(int(2e9))
from collections import Counter, deque
lt, rt, pos = Counter(), Counter(), Counter() #lt记录此节点的左节点 pos记录中序的下标
N = 100
def bulid(il, ir, pl, pr):
root = postorder[pr] # 后序的最后一点为根
k = pos[root] # 找到根在中序中的下标
prr = k - 1 - il + pl
if il < k:
lt[root] = bulid(il, k - 1, pl, prr)
if ir > k:
rt[root] = bulid(k + 1, ir, prr + 1, pr - 1)
return root
def bfs(root):
q = deque()
q.appendleft(root)
while q:
root = q.pop()
print(root, end=" ")
if lt.get(root):
q.appendleft(lt[root])
if rt.get(root):
q.appendleft(rt[root])
n = int(input())
postorder = list(map(int, input().split()))
inorder = list(map(int, input().split()))
for i in range(n):
pos[inorder[i]] = i
root = bulid(0, n - 1, 0, n - 1) #分别代表此时子树的 中序的左右端点 后序的左右端点
bfs(root)