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

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

输入：
[1,2,4,5,3],[4,2,5,1,3]
返回值：
[1,3,5]

思路：
先通过前序遍历序列和中序遍历序列构造出二叉树，再通过bfs或者dfs打印出二叉树的右视图

方法一：递归+bfs
对于任意一颗树而言，前序遍历的形式总是
[ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]

即根节点总是前序遍历中的第一个节点。而中序遍历的形式总是
[ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]

• 用Map保存中序遍历的值和对应索引，关键可以快速定位每一次根结点的位置

• 在中序遍历中定位到根节点，知道左子树和右子树中的节点数目。由于同一颗子树的前序遍历和中序遍历的长度显然是相同的，因此我们就可以对应到前序遍历的结果中，
  对上述形式中的所有左右括号进行定位。

• 递归地构造出左子树和右子树，再将这两颗子树接到根节点的左右位置。
  递归终止条件：当子树先序遍历为空，说明已经越过叶子结点，此时返回null

再通过层序遍历，从左往右，一次入队一层的结点，将每一层结点的最右边结点添加到ArrayList中，因为数组长度需要可以动态扩展，因此先用ArrayList,后面将ArrayList转换为数组

代码如下：

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求二叉树的右视图
     * @param xianxu int整型一维数组 先序遍历
     * @param zhongxu int整型一维数组 中序遍历
     * @return int整型一维数组
     */
     Map<Integer,Integer>map=new HashMap();
    public int[] solve (int[] xianxu, int[] zhongxu) {
        // write code here

        for(int i=0;i<zhongxu.length;i++)
        {
            map.put(zhongxu[i],i);// 用Map保存中序遍历的值和对应索引
        }
        TreeNode root=build(xianxu,0,xianxu.length-1,zhongxu,0,zhongxu.length-1);
        return bfs(root);

    }
    TreeNode build(int[]xianxu,int xstart,int xend,int[]zhongxu,int zstart,int zend)
    {
        if(xstart>xend)return null;
        int rootval=xianxu[xstart];
        int index=map.get(rootval);//快速定位每一次根结点的位置
        int length=index-zstart;
        TreeNode root=new TreeNode(rootval);//构造根结点
        root.left=build(xianxu,xstart+1,xstart+length,zhongxu,zstart,index-1);//递归构造左子树
        root.right=build(xianxu,xstart+length+1,xend,zhongxu,index+1,zend);//递归构造右子树
        return root;
    }

    int[] bfs(TreeNode root)
    {
        if(root==null)return null;
        Deque<TreeNode>dq=new LinkedList<>();
        List<Integer>list=new ArrayList<>();
        dq.offer(root);
        for(TreeNode temp=root;!dq.isEmpty();)
        {
            //每一层结点数不同，因此队列的大小是不断变化的
            for(int size=dq.size();size>0;size--){
                //每次出队一个结点
                temp=dq.poll();
                if(temp.left!=null)dq.offerLast(temp.left);
                if(temp.right!=null)dq.offerLast(temp.right);

            }
            //数组添加的是每一层最后出队的结点，即最右边的结点
            list.add(temp.val);
        }   
        return list.stream().mapToInt(Integer::valueOf).toArray();
    }
}

复杂度分析：
时间复杂度：每个节点都入队出队了 1 次，所以bfs的时间复杂度为，递归次数为，每次递归定位根结点位置时间复杂度为常数级,因此时间复杂度为
空间复杂度： ，递归栈，哈希表和队列大小都为。

方法二：递归+dfs
定义两个栈，记录搜索时经过的结点，记录对应结点的深度，定义一个哈希表（避免同一深度的结点重复入栈）存储二叉树右视图的结点
先将根结点入栈，栈非空时，结点出栈，对应结点的深度值出栈，维护二叉树的最大深度(方便后面将右视图对应深度的值转化为数组），如果不存在对应深度的结点，我们将结点插入右视图，继续将当前结点的左孩子和右孩子入栈，对应深度值入栈，注意先将左孩子入栈再将右孩子入栈，由于栈“先进后出”的特点，相同深度的左孩子和右孩子出栈时，右孩子会先出栈，并且插入右视图中，这样保证了哈希表中存储的是二叉树的右视图、
题目要求返回右视图的数组，将的value值存入数组并返回

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求二叉树的右视图
     * @param xianxu int整型一维数组 先序遍历
     * @param zhongxu int整型一维数组 中序遍历
     * @return int整型一维数组
     */
     Map<Integer,Integer>map=new HashMap();
    public int[] solve (int[] xianxu, int[] zhongxu) {
        // write code here

        for(int i=0;i<zhongxu.length;i++)
        {
            map.put(zhongxu[i],i);//用Map保存中序遍历的值和对应索引
        }
        TreeNode root=build(xianxu,0,xianxu.length-1,zhongxu,0,zhongxu.length-1);
        return dfs(root);

    }
    TreeNode build(int[]xianxu,int xstart,int xend,int[]zhongxu,int zstart,int zend)
    {
        if(xstart>xend)return null;
        int rootval=xianxu[xstart];
        int index=map.get(rootval);//快速定位每一次根结点的位置
        int length=index-zstart;
        TreeNode root=new TreeNode(rootval);
        root.left=build(xianxu,xstart+1,xstart+length,zhongxu,zstart,index-1);//递归构造左子树
        root.right=build(xianxu,xstart+length+1,xend,zhongxu,index+1,zend);//递归构造右子树
        return root;
    }

    int[] dfs(TreeNode root) {
        Map<Integer, Integer> rightValueAtDepth = new HashMap<Integer, Integer>();//存储右视图的结点
        int max_depth = -1;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        Stack<Integer> depthStack = new Stack<Integer>();
        stack.push(root);
        depthStack.push(0);

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            int depth = depthStack.pop();
            if (node != null) {
                // 维护二叉树的最大深度
                max_depth = Math.max(max_depth, depth);
                // 如果不存在对应深度的节点我们才插入
                if (!rightValueAtDepth.containsKey(depth)) {
                    rightValueAtDepth.put(depth, node.val);
                }

                stack.push(node.left);//左孩子先进右孩子后进，保证出栈时右孩子先出
                stack.push(node.right);
                depthStack.push(depth + 1);
                depthStack.push(depth + 1);
            }
        }
        List<Integer> list = new ArrayList<Integer>();
        for (int depth = 0; depth <= max_depth; depth++) {
            list.add(rightValueAtDepth.get(depth));
        }
        return list.stream().mapToInt(Integer::valueOf).toArray();
    }

}

复杂度分析：
时间复杂度 : 深度优先搜索最多访问每个结点一次，因此是线性复杂度,递归建树的时间复杂度也是,所以总的时间复杂度为。
空间复杂度 : 。最坏情况下，栈内会包含接近树高度的结点数量，占用空间为,递归栈的大小也不超过。
（是树中的节点个数）