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

import java.util.*;


public class Solution {
    private static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    /**
     * @param preorder   根左右
     * @param inorder    左根右
     * @return           右视图数组
     */
    public int[] solve (int[] preorder, int[] inorder) {
        TreeNode root = rebuild(preorder,inorder,0,preorder.length-1,0,inorder.length-1);
        ArrayList<Integer> res = new ArrayList<>();
        getRightView(root,res);
        //将结果转换为数组返回
        int[] ret = new int[res.size()];
        for (int i = 0; i < res.size(); i++) {
            ret[i] = res.get(i);
        }
        return ret;
    }

    /**
     * 递归重建二叉树
     * @param preorder   先序遍历数组
     * @param inorder    中序遍历数组
     * @param pStart     先序中开始下标
     * @param pEnd       先序中结束下标
     * @param iStart     中序中开始下标
     * @param iEnd       中序中结束下标
     * @return           根节点
     */
    private TreeNode rebuild(int[] preorder, int[] inorder, int pStart, int pEnd, int iStart, int iEnd) {
        //终止条件
        if (pEnd < pStart || iEnd < iStart) {
            return null;
        }
        //构造根节点
        TreeNode root = new TreeNode(preorder[pStart]);
        //在中序中找到根节点对应的下标
        //因为题目中规定输入合法且无重复值,则在中序遍历中一定可以找到根节点对应的下标
        int index = iStart;
        while (inorder[index] != preorder[pStart]) {
            index++;
        }
        //递归构建左子树和右子树
        root.left = rebuild(preorder,inorder,pStart+1,pStart+index-iStart,iStart,index-1);
        root.right = rebuild(preorder,inorder,pStart+index-iStart+1,pEnd,index+1,iEnd);
        return root;
    }

    /**
     * 以根右左的顺序遍历,同时通过全局变量 deep 记录深度,每次达到一个新的深度的时候将该结点的 val 放在 res 中
     * @param root   根节点
     * @param res    记录遍历结果的链表
     */
    private int deep = 0;
    private void getRightView(TreeNode root, ArrayList<Integer> res) {
        if (root == null) {
            return;
        }
        //维护当前深度
        deep++;
        //判断一下当前是不是到达了这个树新的深度
        //因为没到一个新的深度,我们都会往 res 中加一个元素
        //因此我们通过 res 和 deep 的关系来判断
        if (deep > res.size()) {
            res.add(root.val);
        }
        //继续遍历
        getRightView(root.right,res);
        getRightView(root.left,res);
        //维护深度
        deep--;
        return;
    }
}