做耳鼻喉医院网站多少钱,西部数码网站管理助手 mssql,中国制造加工网官网,企业logo查询网给定一个二叉树的 根节点 root#xff0c;想象自己站在它的右侧#xff0c;按照从顶部到底部的顺序#xff0c;返回从右侧所能看到的节点值。 树这类问题用的最多的就是递归#xff0c;因为树具有天然的递归结构#xff1a; 我们来分析一下题目#xff0c;给定一棵树根结… 给定一个二叉树的 根节点 root想象自己站在它的右侧按照从顶部到底部的顺序返回从右侧所能看到的节点值。 树这类问题用的最多的就是递归因为树具有天然的递归结构 我们来分析一下题目给定一棵树根结点求出每层的最右边的结点是不是我们可以换个角度想是不是相当于求树每层的最右边的结点将一整棵树分成一层一层的进行看待这是不是与我们学过的树的层序遍历有关来我们开始写代码 因为我们既要关注结点的值还要关注结点的所在的层数一般碰到我们需要关注的该物体的属性在2个或者2个以上时这时候我们就需要手动的去创建一个Piar对对其进行封装 public class pair{private TreeNode node;private Integer level;public pair(TreeNode node,Integer level){this.levellevel;this.nodenode;}} 树的层序遍历是通过BFS实现的实现的数据结构肯定不能少
Queuepair queuenew LinkedList(); 因为我们需要返回一个ListInteger,题目让返回什么我们就先给它创建什么 ListListInteger listnew ArrayList();ListInteger pathnew ArrayList(); 然后就开始套用BFS模板进行解答 queue.add(start);while(!queue.isEmpty()){int valqueue.poll();...if(node.left!null){queue.add(...);}if(node.right!null){queue.add(...);} 通过BFS遍历之后我们就会得到一个类似于这样的存储结点的链表是不是我们所需要的是每个链表中的最后一个元素我们将每个小链表拿出来将每个中最后一个元素取出放到一个新的链表中那么这个新的链表不就是我们想要求的最终列表链表么 ListInteger resultnew ArrayList(list.size());for (ListInteger item:list) {result.add(item.get(item.size()-1));}
第一种方法的源码 public ListInteger rightSideView(TreeNode root) {ListListInteger listnew ArrayList();ListInteger pathnew ArrayList();if(rootnull){return path;}Queuepair queuenew LinkedList();queue.add(new pair(root,0));while(!queue.isEmpty()){pair pairqueue.poll();TreeNode nodepair.node;Integer levelpair.level;if(list.size()level){list.add(new ArrayList());}ListInteger list2list.get(level);list2.add(node.val);if(node.left!null){queue.add(new pair(node.left,level1));}if(node.right!null){queue.add(new pair(node.right,level1));}}ListInteger resultnew ArrayList(list.size());for (ListInteger item:list) {result.add(item.get(item.size()-1));}return result;}public class pair{private TreeNode node;private Integer level;public pair(TreeNode node,Integer level){this.levellevel;this.nodenode;}} 这样一来我们这道题的解决完了下面给大家提供一种新的思路递归 因为树是天然的递归结构每层的最右边的结点是不是一般在某棵数的右子树存在的时候中所以我们可以先递归右子树、后递归左子树 DG(root.right);DG(root.left); 我们怎么才能获得最右边的节点呢这样是不是和我们刚才讲的思路相差不多树的高度我们可以在递归的时候将树的高度当做参数传下去然后我们就可以写成 private void DG(TreeNode root, int depth) {DG(root.right,depth1);DG(root.left,depth1);} 递归的两要素递归结束条件递归操作
那么是不是当我们这个结点为空时直接return出去就好了 if(rootnull){return;}
我们还应该声明一个容器去存储我们得到的结果直接看源代码 ListInteger listnew ArrayList();public ListInteger rightSideView(TreeNode root) {if(rootnull){return list;}DG(root,0);return list;}private void DG(TreeNode root, int depth) {if(rootnull){return;}if(depthlist.size()){list.add(root.val);}DG(root.right,depth1);DG(root.left,depth1);} 这里一定有人回问这里为什么是当depthlist.size()的时候会将这个结点加入list中去这种问题对于读递归不是很熟的东西确实是比较难以捉摸的原因是这样的因为我们在递归的时候是优先递归的是右子树后递归的左子树所以每次都是每层的最右边的那个节点优先到达的这层所以才往我们的结果集中加入当前节点所以才会这么写
