牛客算法题——输出二叉树的右视图

题目描述

请根据二叉树的前序遍历，中序遍历恢复二叉树，并且打印出二叉树的右视图。

示例

[in]>>[1,2,4,5,3],[4,2,5,1,3]

[out]>>[1,3,5]

解决方法

想解决这个问题，第一步需要根据前序遍历和中序遍历来重建二叉树。

从前序遍历和中序遍历重建思路：

1. 首先由前序遍历的第一个节点确定其为根节点root
2. 在中序遍历的结果中找到root，这时候可以知道在中序遍历结果中，root左边的节点为左子树的节点，而root右边的节点为右子树的节点。
3. 在左右子树中递归1，2，3步直到节点为空。

def buildTree(self,xianxu,zhongxu):
    if not xianxu:return None
    root = TreeNode(xianxu[0])
    index = zhongxu.index(root.val)
    root.left=self.buildTree(xianxu[1:index+1],zhongxu[:index])
    root.right=self.buildTree(xianxu[index+1:],zhongxu[index+1:])
    return root

（扩展）从后序遍历和中序遍历重建思路：

从中序遍历和后序遍历还原二叉树的方法是一样的，不同的是在找根节点的确认方法不同：后序遍历结果的最后一个节点为根节点。剩下的步骤都是一样的。

def buildTree(self,zhongxu,houxu):
    if not houxu:return None
    root = TreeNode(houxu[-1])
    index = zhongxu.index(root.val)
    root.left=self.buildTree(zhongxu[0:i],houxu[0:i])
    root.right=self.buildTree(zhongxu[i+1],houxu[i:-1])

重建了二叉树之后，我们先搞清楚右视图是什么意思。

右视图：从右边看的每层第一个节点（也就是层次遍历的每层的最后一个节点）

接下来我们就利用层次遍历找到每层的最后一个节点。

def rightView(self,root):
    if not root:return None
    q,rightViewRes=[root],[]
    while q:
        n,level=len(q),[]
        for i in range(0,n):
            node=q.pop(0)
            level.append(node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        rightViewRes.append(level[-1])
    return rightViewRes

把上面的代码综合起来，就能得到上题的解答，完整代码如下：

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
# 求二叉树的右视图
# @param xianxu int整型一维数组 先序遍历
# @param zhongxu int整型一维数组 中序遍历
# @return int整型一维数组
#
class Solution:
    def solve(self , xianxu , zhongxu ):
        return self.rightView(self.buildTree(xianxu,zhongxu))
    def buildTree(self,xianxu,zhongxu):
        if not xianxu:return None
        root = TreeNode(xianxu[0])
        index = zhongxu.index(root.val)
        root.left=self.buildTree(xianxu[1:index+1],zhongxu[:index])
        root.right=self.buildTree(xianxu[index+1:],zhongxu[index+1:])
        return root
    def rightView(self,root):
        if not root:return None
        q,rightView=[root],[]
        while q:
            n,level=len(q),[]
            for i in range(0,n):
                node=q.pop(0)
                level.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            rightView.append(level[-1])
        return rightView
            # write code here