【刷题篇】二叉树的右视图

一、题目

OJ链接
请根据二叉树的前序遍历，中序遍历恢复二叉树，并打印出二叉树的右视图

示例：

对应的输出为[1,3,5]。

二、题解

解决本题主要 分两个步骤：

1. 根据前序和中序构建出二叉树
2. 对二叉树进行层次遍历，找到每一层的最右侧的节点

构建二叉树：
参考链接: 二叉树相关OJ题

中序遍历找出最每一层最右侧的节点：
层序遍历的过程

变量size记录的是当前遍历到的层的节点数，我们在入队的时候的顺序是：从左到右依次将当前层的节点加入到队列中，所以在出队的时候，当前层的最右侧的节点一定是该层所有节点中最后一个出队列的

故我们可根据这一特点，增设一个判断条件，但size为0时，此时上一次出的元素就是当前层的最右侧的元素

源码：

public class Solution {
    
    /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * 求二叉树的右视图 * @param xianxu int整型一维数组 先序遍历 * @param zhongxu int整型一维数组 中序遍历 * @return int整型一维数组 */
    int preIndex=0;
    HashMap<Integer,Integer> map=new HashMap<>();
     public void RootIndex(int[] inorder){
    
        for (int i = 0; i < inorder.length; i++) {
    
            map.put(inorder[i],i);
        }
    }
     public ArrayList<Integer> rightSideView(TreeNode root) {
    
        ArrayList<Integer> res = new ArrayList<Integer>();
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        q.offer(root);
        while(!q.isEmpty()){
    
            //队列中的大小即是这一层的节点树
            int size = q.size();
            while(size-- != 0){
    
                TreeNode temp = q.poll();           
                if(temp.left != null)
                    q.offer(temp.left);
                if(temp.right != null)
                    q.offer(temp.right);
                //最右元素
                if(size == 0)
                    res.add(temp.val);
            }
        }
        return res;
    }
    public int[] solve (int[] xianxu, int[] zhongxu) {
    
           TreeNode root=buildTree(xianxu,zhongxu);
         ArrayList<Integer> tmp=rightSideView(root);
        int[] arr=new int[tmp.size()];
        for(int i=0;i<tmp.size();i++){
    
            arr[i]=tmp.get(i);
        }
        return arr;
    }
    public TreeNode buildTree(int[] xianxu,int[] zhongxu ){
    
         
        RootIndex(zhongxu);
        return buildTreeChild(xianxu,zhongxu,0,zhongxu.length-1);
        
    }
    public TreeNode buildTreeChild(int[] xianxu,int[] zhongxu,int inbegin,int inend){
    
        if(inbegin>inend){
    
            return null;
        }
        TreeNode root=new TreeNode(xianxu[preIndex]);
        int ri=map.get(xianxu[preIndex]);
        preIndex++;
        root.left=buildTreeChild(xianxu,zhongxu,inbegin,ri-1);
        root.right=buildTreeChild(xianxu,zhongxu,ri+1,inend);
        return root;
    }
}