[数据结构与算法]BM41 输出二叉树的右视图

1、题目

2、思路

? ? ? ? 我没有思路。。哭！

3、代码

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求二叉树的右视图
     * @param xianxu int整型一维数组 先序遍历
     * @param zhongxu int整型一维数组 中序遍历
     * @return int整型一维数组
     */
    
    ArrayList<ArrayList<Integer>> lists = new ArrayList<>();
 
    public int[] solve(int[] xianxu, int[] zhongxu) {
        // write code here
        lists.add(new ArrayList<Integer>());
        TreeNode root = Go(xianxu, zhongxu);
        Go2(root, 0);
        ArrayList<Integer> list = new ArrayList<>();
        //将二叉树 层次便利的 每层的额最后一个 值存入新的 ArrayList 中 转化为 数组
        for (int i = 0; i < lists.size(); i++) {
 
            list.add(lists.get(i).get(lists.get(i).size() - 1));
 
        }
        int result[] = list.stream().mapToInt(Integer::valueOf).toArray();
        return result;
    }
 
    //此方法用来重建二叉树
    private TreeNode Go(int[] pre, int[] in) {
        if (pre.length == 0 || in.length == 0) {
            return null;
        }
        TreeNode node = new TreeNode(pre[0]);
        for (int i = 0; i < in.length; i++) {
            if (in[i] == pre[0]) {
                node.left = Go(Arrays.copyOfRange(pre, 1, i + 1), Arrays.copyOfRange(in, 0, i));
                node.right = Go(Arrays.copyOfRange(pre, i + 1, pre.length), Arrays.copyOfRange(in, i + 1, in.length));
                break;
 
            }
        }
 
        return node;
    }
 
    //此方法用来 二叉树的 层次遍历到 ArrayList<ArrayList<Integer>>中
    private void Go2(TreeNode root, int flag) {
        if (lists.size() < flag + 1) {
            lists.add(new ArrayList<Integer>());
        }
        lists.get(flag).add(root.val);
        if (root.left != null)
            Go2(root.left, flag + 1);
        if (root.right != null)
            Go2(root.right, flag + 1);
    }
  
    
    
}