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

import java.util.*;

public class Solution {
    public TreeNode getTree(int[] pre, int[] vin){
        if(pre.length==0){
            return null;
        }
        TreeNode root = new TreeNode(pre[0]);
        for(int i=0;i<vin.length;++i){
            if(pre[0]==vin[i]){
                root.left = getTree(Arrays.copyOfRange(pre,1,i+1),Arrays.copyOfRange(vin,0,i));
                root.right = getTree(Arrays.copyOfRange(pre,i+1,pre.length),Arrays.copyOfRange(vin,i+1,vin.length));
                break;
            }
        }
        return root;
    }

    public ArrayList<Integer> rightSideView(TreeNode root){
        //存储最右边的值,第一个为深度，第二个为最右边的值
        Map<Integer,Integer> mp = new HashMap<Integer,Integer>();
        //记录最大深度，方便在遍历是知道下标的上界
        int max_depth = -1;
        //维护深度访问时的节点
        Stack<TreeNode> nodes = new Stack<TreeNode>();
        //维护每个节点的深度
        Stack<Integer> depths = new Stack<Integer>();
        nodes.push(root);
        depths.push(0);
        while(!nodes.isEmpty()){
            TreeNode node = nodes.pop();
            int depth = depths.pop();
            if(node!=null){
                //更新最大深度
                max_depth = Math.max(max_depth,depth);
                //关键：map中只有对应深度不存在节点时才插入
                if(mp.get(depth)==null){
                    mp.put(depth,node.val);
                }
                //已存入最右节点则左右孩子入栈准备向下遍历
                nodes.push(node.left);
                nodes.push(node.right);
                depths.push(depth+1);
                depths.push(depth+1);
            }
        }
        ArrayList<Integer> res = new ArrayList<Integer>();
        //将栈的值赋值给数组
        for(int i=0;i<=max_depth;++i){
            res.add(mp.get(i));
        }
        return res;
    }

    public int[] solve (int[] preOrder, int[] inOrder) {
        if(preOrder.length==0){
            return new int[0];
        }
        //构建二叉树
        TreeNode root = getTree(preOrder,inOrder);
        //获取右视图动态数组
        ArrayList<Integer> temp = rightSideView(root);
        int[] res = new int[temp.size()];
        //动态数组转为普通int数组
        for(int i=0;i<temp.size();++i){
            res[i] = temp.get(i);
        }
        return res;
    }
}

方法：二叉树递归 + 二叉搜索树

用上一题的知识通过两个先序和中序数组构建二叉树，难点在于如何采用二叉搜索树获取右视图。需要用到map结构存储对应深度的最右结点值，所以需要维护两个栈用来存储要遍历的节点和深度，还需要维护一个最大深度值方便后续遍历赋值。利用栈的先进后出特性，先让左节点入栈再让右节点入栈，这样每次出栈的第一个结点就是右视图需要的结点。

1、构建二叉树

2、获取右视图

3、第二个函数中，定义map和两个栈，初始将根节点和深度0入栈，进入循环，循环条件是栈不为空。出栈，结点非空才进行更新最大深度和入栈，在map中只有当当前深度下不存在时才插入新值，这个就是所求的右视图节点值。然后让左右子树分别入结点栈，相应的深度栈在当前的深度加一后也入栈一个结点入一次栈所以是两次。

4、待循环结束后将map中的值复制到动态数组中

5、主函数在获取到右视图动态数组后再转为普通int数组，返回即可