PAT甲级：1020 Tree Traversals

题目描述：

Suppose that all the keys in a binary tree are distinct positive integers. Given the postorder and inorder traversal sequences, you are supposed to output the level order traversal sequence of the corresponding binary tree.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (≤30), the total number of nodes in the binary tree. The second line gives the postorder sequence and the third line gives the inorder sequence. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print in one line the level order traversal sequence of the corresponding binary tree. All the numbers in a line must be separated by exactly one space, and there must be no extra space at the end of the line.

Sample Input:

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

Sample Output:

4 1 6 3 5 7 2

代码长度限制

16 KB

时间限制

400 ms

内存限制

64 MB

题目大意：给定一棵树的后序遍历和中序遍历 输出这棵树的层序遍历

解题思路：

题目的突破口是：一棵树或者一棵子树的根节点一定在后序遍历数组中的最后一个位置

所以我们可以选确定当前树的根节点是什么数字 再确定该数字在中序遍历中的下标 然后再分左右子树分别递归即可 注意中序遍历的左子树应该是inoder[:index_root],右子树应该是inorder[index_root+1:]. 而后序遍历的左右子树可以通过中序遍历的子树长度求出 因为后序遍历和中序遍历的左子树和右子树的长度应该是对应相等的

最后从根节点bfs一遍即可求出层序遍历的结果

class TreeNode(object) :
    def __init__(self,x) :
        self.val = x
        self.left = None
        self.right = None
        
def buildTree(posto,ino) :
    if not posto : return None
    
    root = TreeNode(posto[-1]) # #根节点为后序遍历的末位
    root_index = ino.index(posto[-1]) # 确定中序遍历中，根节点的下标
    
    # 根据根节点下标设立中序遍历的左右子树
    lefti = ino[:root_index]
    righti = ino[root_index+1:]
    
    length = len(lefti) # 确定左子树长度 关键点：后序遍历和中序遍历的子树长度应该相同
    
    # 根据中序遍历左子树长度确定后序遍历的左右子树
    leftp = posto[:length]
    rightp = posto[length:-1]
    
    root.left = buildTree(leftp,lefti)
    root.right = buildTree(rightp,righti)
    
    return root # 每个节点的左右子节点应该是子树的根节点
    
def bfs(root) : # 输出层序遍历
    if root == None : return
    queue = [root]
    head = 0
    while queue :
        print(queue[head].val)
        if queue[head].left != None : queue.append(queue[head].left)
        if queue[head].right != None : queue.append(queue[head].right)
        queue.pop(0)
        
n = int(input())
posto = list(map(int,input().split())) # 后序遍历
ino = list(map(int,input().split())) # 中序遍历

root = buildTree(posto,ino)
bfs(root)