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

思路

1）先通过前序遍历序列和中序遍历序列重建一棵二叉树(想知道如何具体实现的，可以看一看我这篇博客，里面有很详细的讲解，谢谢)

#重建二叉树(https://blog.nowcoder.net/n/897d1e8c90aa4bfbb8f6798359068ca5)

实现二叉树的重建代码如下

public TreeNode createTree (LinkedList<Integer> pre, ArrayList<Integer> vin, HashMap<Integer, Integer> nodeIndexs, int start, int end) {
        if (start > end || pre.isEmpty()) {
            return null;
        }
        if (start == end) {
            return new TreeNode(pre.poll());
        }
        int val = pre.poll();
        TreeNode root = new TreeNode(val);
        int index = nodeIndexs.get(val);
        TreeNode leftChild = createTree(pre, vin, nodeIndexs, start, index - 1);
        TreeNode rightChild = createTree(pre, vin, nodeIndexs, index + 1, end);
        root.left = leftChild;
        root.right = rightChild;
        return root;
    }

2）然后，通过反向的广度优先遍历(即对于每一层来说，从右往左进行遍历)，遍历中每一层的第一个节点就是全部加入到一个数组中，就是题目要求的右视图啦。

实现输出二叉树的右视图代码如下

public int[] rightView (TreeNode root) {
        if (null == root) {
            return new int[]{};
        }
        if (null == root.left && null == root.right) {
            return new int[]{root.val};
        }
         
        LinkedList<TreeNode> queue = new LinkedList<>();
        TreeNode tmpNode = root;
        HashMap<TreeNode, Integer> nodeLevels = new HashMap<>();
        int level = 1;
        ArrayList<Integer> arrayList = new ArrayList<>();
         
        queue.add(tmpNode);
        nodeLevels.put(tmpNode, 1);
        arrayList.add(tmpNode.val);
         
        while (!queue.isEmpty()) {
             
            tmpNode = queue.poll();
            if (nodeLevels.get(tmpNode) > level) {
                arrayList.add(tmpNode.val);
                level = nodeLevels.get(tmpNode);
            }
             
            if (null != tmpNode.right) {
                queue.add(tmpNode.right);
                nodeLevels.put(tmpNode.right, nodeLevels.get(tmpNode) + 1);
            }
            if (null != tmpNode.left) {
                queue.add(tmpNode.left);
                nodeLevels.put(tmpNode.left, nodeLevels.get(tmpNode) + 1);
            }
        }
        return arrayList.stream().mapToInt(Integer::intValue).toArray();
    }

完整代码如下

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求二叉树的右视图
     * @param xianxu int整型一维数组 先序遍历
     * @param zhongxu int整型一维数组 中序遍历
     * @return int整型一维数组
     */
    public int[] solve (int[] xianxu, int[] zhongxu) {
        // write code here
        if (0 == xianxu.length) {
            return new int[]{};
        }
        if (1 == xianxu.length) {
            return xianxu;
        }
        
        LinkedList<Integer> pre = new LinkedList<>();
        ArrayList<Integer> vin = new ArrayList<>();
        HashMap<Integer, Integer> nodeIndexs = new HashMap<>();
        
        for (int val : xianxu) {
            pre.add(val);
        }
        for (int i = 0; i < zhongxu.length; i++) {
            vin.add(zhongxu[i]);
            nodeIndexs.put(zhongxu[i], i);
        }
        
        TreeNode root = createTree(pre, vin, nodeIndexs, 0, vin.size() - 1);
        return rightView(root);
    }
    
    public TreeNode createTree (LinkedList<Integer> pre, ArrayList<Integer> vin, HashMap<Integer, Integer> nodeIndexs, int start, int end) {
        if (start > end || pre.isEmpty()) {
            return null;
        }
        if (start == end) {
            return new TreeNode(pre.poll());
        }
        int val = pre.poll();
        TreeNode root = new TreeNode(val);
        int index = nodeIndexs.get(val);
        TreeNode leftChild = createTree(pre, vin, nodeIndexs, start, index - 1);
        TreeNode rightChild = createTree(pre, vin, nodeIndexs, index + 1, end);
        root.left = leftChild;
        root.right = rightChild;
        return root;
    }
    
    public int[] rightView (TreeNode root) {
        if (null == root) {
            return new int[]{};
        }
        if (null == root.left && null == root.right) {
            return new int[]{root.val};
        }
        
        LinkedList<TreeNode> queue = new LinkedList<>();
        TreeNode tmpNode = root;
        HashMap<TreeNode, Integer> nodeLevels = new HashMap<>();
        int level = 1;
        ArrayList<Integer> arrayList = new ArrayList<>();
        
        queue.add(tmpNode);
        nodeLevels.put(tmpNode, 1);
        arrayList.add(tmpNode.val);
        
        while (!queue.isEmpty()) {
            
            tmpNode = queue.poll();
            if (nodeLevels.get(tmpNode) > level) {
                arrayList.add(tmpNode.val);
                level = nodeLevels.get(tmpNode);
            }
            
            if (null != tmpNode.right) {
                queue.add(tmpNode.right);
                nodeLevels.put(tmpNode.right, nodeLevels.get(tmpNode) + 1);
            }
            if (null != tmpNode.left) {
                queue.add(tmpNode.left);
                nodeLevels.put(tmpNode.left, nodeLevels.get(tmpNode) + 1);
            }
        }
        return arrayList.stream().mapToInt(Integer::intValue).toArray();
    }
}