输出二叉树的右视图

日常看不懂系列

  public TreeNode buildTree(int[] xianxu,int l1,int r1,int[] zhongxu,int l2,int r2){
       if(l1>r1||l2>r2){
           return null;
       }

       TreeNode root=new TreeNode(xianxu[l1]);

       int rootIndex=0;

       for (int i=l2;i<=r2;i++){
           if(zhongxu[i]==xianxu[l1]){
               rootIndex=i;
               break;
           }
       }

       int leftsize=rootIndex-l2;
       int rightsize=r2-rootIndex;
       root.left=buildTree(xianxu,l1+1,l1+leftsize,zhongxu,l2,l2+leftsize-1);
       root.right=buildTree(xianxu,r1-rightsize+1,r1,zhongxu,rootIndex+1,r2);
       return root;
   }

   public ArrayList<Integer> rightSideView(TreeNode root){
       Map<Integer,Integer> mp=new HashMap<Integer,Integer>();
       int max_depth=-1;
       Stack<TreeNode> nodes=new Stack<TreeNode>();
       Stack<Integer> depths=new Stack<Integer>();
       nodes.push(root);
       depths.push(0);
       while (!nodes.isEmpty()){
           TreeNode node=nodes.pop();
           int depth=depths.pop();
           if(node!=null){
               max_depth=Math.max(max_depth,depth);
               if(mp.get(depth)==null) mp.put(depth,node.val);
               nodes.push(node.left);
               nodes.push(node.right);
               depths.push(depth+1);
               depths.push(depth+1);
           }
       }
       ArrayList<Integer> res=new ArrayList<Integer>();

       for (int i=0;i<=max_depth;i++){
           res.add(mp.get(i));
       }

       return res;
   }
   public int[] solve(int[] xianxu,int[] zhongxu){
       if(xianxu.length==0) return new int[0];

       TreeNode root=buildTree(xianxu,0,xianxu.length-1,zhongxu,0,zhongxu.length-1);
       ArrayList<Integer> temp=rightSideView(root);
       int[] res=new int[temp.size()];
       for (int i=0;i< temp.size();i++){
           res[i]=temp.get(i);
       }
       return res;

   }


全部评论

相关推荐

07-17 12:07
门头沟学院 Java
勇敢牛牛不怕困难
投递OPPO等公司7个岗位
点赞 评论 收藏
分享
流浪的神仙:无恶意,算法一般好像都得9硕才能干算法太卷啦
点赞 评论 收藏
分享
Twilight_m...:表格简历有点难绷。说说个人看法: 1.个人基本情况里好多无意义信息,什么婚姻状况、健康状况、兴趣爱好、户口所在地、身份证号码、邮政编码,不知道的以为你填什么申请表呢。 2.校内实践个人认为对找工作几乎没帮助,建议换成和测开有关的项目,实在没得写留着也行。 3.工作经历完全看不出来是干什么的,起码看着和计算机没啥关系,建议加强描述,写点你在工作期间的实际产出、解决了什么问题。 4.个人简述大而空,看着像AI生成,感觉问题最大。“Python,C,C++成为我打造高效稳定服务的得力工具”、“我渴望凭借自身技术知识与创新能力,推动人工智能技术的应用发展,助力社会实现智能化转型”有种小学作文的美感。而且你确定你个人简述里写的你都会嘛?你AI这块写的什么“深入研究”,发几篇顶会的硕博生都不一定敢这么写。而且你AI这块的能力和软测也完全无关啊。个人简述建议写你对哪些技术栈、哪些语言、哪些生产工具的掌握,写的有条理些,而且最好是和测开强相关的。
点赞 评论 收藏
分享
07-15 11:43
门头沟学院 Java
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务