网站和浏览器不兼容,seo免费软件,网站建设设,网站在线留言怎么做文章目录 题目方法一#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);//切换到下一层继续找第一次访问的元素}
