题解 | #输出二叉树的右视图#

先重建二叉树，再用层次遍历打印右视图

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
# 求二叉树的右视图
# @param xianxu int整型一维数组 先序遍历
# @param zhongxu int整型一维数组 中序遍历
# @return int整型一维数组
#
class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def solve(self , xianxu , zhongxu ):
        # write code here
        def helper(preorder, lo_pre, hi_pre, inorder, lo_in, hi_in):
            if hi_pre < lo_pre or hi_in < lo_in:
                return None
            root_value = preorder[lo_pre]
            head = TreeNode(root_value)

            root_index = inorder.index(root_value)
#             print(lo_pre+1, lo_pre+temp, lo_in, temp-1)
#             print(temp+lo_pre+1, hi_pre,temp+1, hi_in)
            head.left = helper(xianxu, lo_pre+1, lo_pre+root_index-lo_in, zhongxu, lo_in, root_index-1)
            head.right = helper(xianxu, root_index-lo_in+lo_pre+1, hi_pre, zhongxu, root_index+1, hi_in)
            return head
        root = helper(xianxu, 0, len(xianxu)-1, zhongxu, 0, len(zhongxu)-1)

        def postOrder(node):
            if not node:
                return
            postOrder(node.left)
            postOrder(node.right)
            print(node.val)
        print("postOrder:")
        postOrder(root)
        def levelOrder(root):
            res = []
            if not root:
                return res
            q = [root]
            while q:
                length = len(q)
                curr = None
                for i in range(length):
                    curr = q[0]
                    q = q[1::]
                    if curr.left:
                        q.append(curr.left)
                    if curr.right:
                        q.append(curr.right)
                res.append(curr.val)
            return res

        res = levelOrder(root)

        return res