【必会】BM41 输出二叉树的右视图【中等+】

输出二叉树的右视图_牛客题霸_牛客网【牛客题霸】收集各企业高频校招笔面试题目，配有官方题解，在线进行百度阿里腾讯网易等互联网名企笔试面试模拟考试练习,和牛人一起讨论经典试题,全面提升你的技术能力https://www.nowcoder.com/practice/c9480213597e45f4807880c763ddd5f0?tpId=295&tqId=1073834&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D295

题目：

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

数据范围： 0≤n≤10000

要求： 空间复杂度 O(n)，时间复杂度 O(n)

如输入[1,2,4,5,3],[4,2,5,1,3]时，通过前序遍历的结果[1,2,4,5,3]和中序遍历的结果[4,2,5,1,3]可重建出以下二叉树：

所以对应的输出为[1,3,5]。

示例1

输入：

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

返回值：

[1,3,5]

备注：

二叉树每个节点的值在区间[1,10000]内，且保证每个节点的值互不相同。

思路：

• 两步：
  • 根据前序遍历和中序遍历恢复二叉树；105. 从前序与中序遍历序列构造二叉树
  • 使用层序遍历获取右视图；199. 二叉树的右视图
  • 是这两个题目的综合；

• 从中序遍历中找到前序遍历中的根节点可以使用哈希表进行优化，用空间换时间，可以先遍历中序遍历，将中序遍历中的坐标和值的关系存在哈希表中；
• 其实有点分治的感觉；

代码：

import java.util.*;
public class Solution {
    private Map<Integer, Integer> indexMap;
    //建树函数
    //四个int参数分别是前序最左节点下标，前序最右节点下标
    //中序最左节点下标，中序最右节点坐标
    public TreeNode myBuildTree(int[] preorder, int[] inorder, int preorder_left,
                                int preorder_right, int inorder_left, int inorder_right) {
        // 左闭右闭就会影响这个弹出条件，这就导致了如果是空的时候右边会是负数；
        if (preorder_left > preorder_right) {
            return null;
        }
        // 前序遍历中的第一个节点就是根节点；
        int preorder_root = preorder_left;
        // 在中序遍历中定位根节点；
        int inorder_root = indexMap.get(preorder[preorder_root]);
        // 先把根节点建立出来；
        TreeNode root = new TreeNode(preorder[preorder_root]);
        // 从中序遍历中得到左子树中的节点数目；
        int size_left_subtree = inorder_root - inorder_left;
        // 递归地构造左子树，并连接到根节点；
        // 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素；
        root.left = myBuildTree(preorder, inorder, preorder_left + 1,
                                preorder_left + size_left_subtree, inorder_left, inorder_root - 1);
        // 递归地构造右子树，并连接到根节点
        // 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素；
        root.right = myBuildTree(preorder, inorder,
                                 preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1,
                                 inorder_right);
        return root;
    }

    //层次遍历
    public ArrayList<Integer> rightSideView(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        q.offer(root);
        while (!q.isEmpty()) {
            //队列中的大小即是这一层的节点树
            int size = q.size();
            while (size-- != 0) {
                TreeNode temp = q.poll();
                if (temp.left != null)
                    q.offer(temp.left);
                if (temp.right != null)
                    q.offer(temp.right);
                //最右元素
                if (size == 0)
                    res.add(temp.val);
            }
        }
        return res;
    }

    public int[] solve (int[] preorder, int[] inorder) {
        int n = preorder.length;
        // 构造哈希映射，帮助我们快速定位根节点
        indexMap = new HashMap<Integer, Integer>();
        for (int i = 0; i < n; i++) {
            indexMap.put(inorder[i], i);
        }
        //建树
        TreeNode root = myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
        //获取右视图输出
        ArrayList<Integer> temp = rightSideView(root);
        //转化为数组
        int[] res = new int[temp.size()];
        for (int i = 0; i < temp.size(); i++)
            res[i] = temp.get(i);
        return res;
    }
}