NC136：输出二叉树的右视图

解法：重建+右视图：
① 根据先序、中序遍历重构二叉树
② 层序遍历二叉树输出每层最右侧元素
步骤一：根据先序、中序遍历重构二叉树:
首先找到根节点在中序遍历中的下标，根据此下边可以得到左子树有多少个结点count。
根据根节点的下标以及左子树有多少个结点，将原数组划分为左右子树两部分。通过计算可得到左右子树在原数组的坐标范围。
创建根结点，左右孩子可通过递归左右子树数组得到。
递归结束条件：当先序（中序也行）的左边界大于右边界时返回空。

public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        if (pre == null || in == null)
            return null;
        if (pre.length != in.length)
            return null;
        return constructBinaryTree(pre, 0, pre.length-1, in, 0, in.length-1);
    }
        private TreeNode constructBinaryTree(int[] pre, int startPre, int endPre, int[] in, int startIn, int endIn) {
            if (startPre > endPre || startIn > endIn)
                return null;
            TreeNode root = new TreeNode(pre[startPre]);
            for (int i = startIn; i <= endIn; i++) {
                if (in[i] == pre[startPre]) {
                    root.left = constructBinaryTree(pre, startPre + 1, startPre + i - startIn, in, startIn, i - 1);
                    root.right = constructBinaryTree(pre, startPre + i - startIn + 1, endPre, in, i + 1, endIn);
                }
            }
            return root;
    }

步骤二：层序遍历树得到右视图：
就是在层序遍历的基础上，判断当前结点是不是这一行的最后一个结点，其他不变。

    public int[] rightView(TreeNode root){ 
        ArrayList<Integer> list=new ArrayList<>();
        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            int size=queue.size();
            for(int i=0;i<size;i++){
                TreeNode tmp=queue.poll();
                if(i==size-1){
                    list.add(tmp.val);
                }
                if(tmp.left!=null){
                    queue.add(tmp.left);
                }
                if(tmp.right!=null){
                    queue.add(tmp.right);
                }
            }
        }
        int[] res=new int[list.size()];
        for(int i=0;i<list.size();i++){
            res[i]=list.get(i);
        }
        return res;
    }

综合代码：

    public int[] solve (int[] xianxu, int[] zhongxu) {
        // write code here
        if(xianxu.length == 0){
            return new int[0];
        }
        TreeNode root=reConstructBinaryTree(xianxu,zhongxu);
        return rightView(root);
    }

    public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        if (pre == null || in == null)
            return null;
        if (pre.length != in.length)
            return null;
        return BinaryTree(pre, 0, pre.length-1, in, 0, in.length-1);
    }

    public TreeNode BinaryTree(int[] pre,int sPre,int ePre,int[] in,int sIn,int eIn){
        if(sPre>ePre || sIn>eIn){
            return null;
        }
        TreeNode root=new TreeNode(pre[sPre]);
        for(int i=sIn;i<=eIn;i++){
            if(in[i]==pre[sPre]){
                root.left=BinaryTree(pre,sPre+1,sPre+i-sIn,in,sIn,i-1);
                root.right=BinaryTree(pre,sPre+i-sIn+1,ePre,in,i+1,eIn);
            }
        }
        return root;
    }

    public int[] rightView(TreeNode root){ 
        ArrayList<Integer> list=new ArrayList<>();
        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            int size=queue.size();
            for(int i=0;i<size;i++){
                TreeNode tmp=queue.poll();
                if(i==size-1){
                    list.add(tmp.val);
                }
                if(tmp.left!=null){
                    queue.add(tmp.left);
                }
                if(tmp.right!=null){
                    queue.add(tmp.right);
                }
            }
        }
        int[] res=new int[list.size()];
        for(int i=0;i<list.size();i++){
            res[i]=list.get(i);
        }
        return res;
    }