PAT1 1020 Tree Traversals

题目链接 我的github

题目大意

给一棵树的后序遍历和中序遍历，现在需要输出它的层次遍历

输入

每组包含一个测试用例，每个样例第一行是一个正整数$N$($\le 30$)，表示树的节点数，第二行给出树的后序遍历，第三行给出树的中序遍历

输出

对每个样例，在一行中输出层次遍历，每个节点之间用空格分开。行尾不能有多余的空格

输入样例

7 2 3 1 5 7 6 4 1 2 3 4 5 6 7

输出样例

4 1 6 3 5 7 2

解析

拿到题就满脑子想着根据树的后序和中序构造出树，然后再层次遍历保存结果。 在做完之后又去搜了下这题的解答，发现有大神不用构造树的解法：传送门 之后可以用python去实现下，现在贴上我的笨重的构造树的解法

class node: def __init__(self, num): self.num = num self.left = None self.right = None n = 0 postOrder = list() inOrder = list() def findFather(a, b, c, d): root = node(-1) if a == b: #找到叶子节点了 root.num = inOrder[a] return root marki = -1 #标记根节点在后序中的下标 markj = -1 #标记根节点在中序中的下标 for i in range(d, c - 1, -1): if marki != -1: break for j in range(a, b + 1): if inOrder[j] == postOrder[i]: marki = i markj = j root.num = inOrder[j] break if markj == a: #如果根节点没有左子树 root.right = findFather(markj + 1, b, c, marki - 1) return root if markj == b: #如果根节点没有右子树 root.left = findFather(a, markj - 1, c, marki - 1) return root root.left = findFather(a, markj - 1, c, marki - 1) root.right = findFather(markj + 1, b, c, marki - 1) return root def levelOrder(root): #层次遍历保存结果 que = list() ans = list() que.append(root) while que: a = que[0] que.pop(0) ans.append(a.num) if a.left: que.append(a.left) if a.right: que.append(a.right) return ans def solve(): global n, postOrder, inOrder n = map(int, input().split()) postOrder = list(map(int, input().split())) inOrder = list(map(int, input().split())) root = findFather(0, len(inOrder) - 1, 0, len(postOrder) - 1) res = levelOrder(root) for i in range(len(res)): print("%d" % res[i], end=('\n' if i == len(res) - 1 else ' ')) if __name__ == "__main__": solve()