中国最好的网站制作公司,网站负责人照片,VIP视频自助网站建设,个人网站设计论文题目文章目录 题目方法一#xff1a;层序遍历取每一层最后一个元素方法二#xff1a;深度优先搜索 题目 方法一#xff1a;层序遍历取每一层最后一个元素
// 方法一 #xff1a;层序 集合(取每层子集合最后一个元素)// ListListInteger Rlist new ArrayList… 文章目录 题目方法一层序遍历取每一层最后一个元素方法二深度优先搜索 题目 方法一层序遍历取每一层最后一个元素
// 方法一 层序 集合(取每层子集合最后一个元素)// ListListInteger Rlist new ArrayList();// public ListInteger rightSideView(TreeNode root) {// if(root null ) return new ArrayList();// QueueTreeNode queue new ArrayDeque();// queue.offer(root); // while(!queue.isEmpty()){// int count queue.size();// ListInteger res new ArrayList();// for(int i0;icount;i){// TreeNode node queue.poll();// res.add(node.val);// if(node.left ! null) queue.offer(node.left);// if(node.right ! null) queue.offer(node.right);// }// Rlist.add(res);//每层节点集合加入到大集合// }// ListInteger result new ArrayList();//结果集// for(List list : Rlist ){// result.add((Integer)list.get(list.size()-1));//取每层集合最后一个元素// }// return result;// }
// 方法一优化 在层序遍历的时候直接要每一层的最后一个元素加入集合 就不需要把一层所有节点的加入集合再去取每层集合最后一个了public ListInteger rightSideView(TreeNode root) {ListInteger Rlist new ArrayList();//结果集if(root null ) return Rlist;QueueTreeNode queue new ArrayDeque();queue.offer(root); while(!queue.isEmpty()){int count queue.size();for(int i0;icount;i){TreeNode node queue.poll();if(i count -1)//只取一层最后一个元素countRlist.add(node.val);if(node.left ! null) queue.offer(node.left);if(node.right ! null) queue.offer(node.right);}}return Rlist;}方法二深度优先搜索
根 右 左 的顺序 取每层第一个被访问到的节点depth list.size() ListInteger result new ArrayList();public ListInteger rightSideView(TreeNode root) {dfs(root,0);//起始递归 root 深度为0return result;}public void dfs(TreeNode tree ,int depth){if(tree null) return ;if(depth result.size()) result.add(tree.val);//若当前深度 集合的大小说明在该层还没加入任何元素此时只需加入第一次访问的元素就行dfs(tree.right,depth1);//切换到下一层继续找第一次访问的元素dfs(tree.left,depth1);//切换到下一层继续找第一次访问的元素}
