首页 > 其他 > 详细

领扣(LeetCode)二叉树的右视图 个人题解

时间:2018-11-15 20:57:48      阅读:319      评论:0      收藏:0      [点我收藏+]

给定一棵二叉树,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。

示例:

输入: [1,2,3,null,5,null,4]
输出: [1, 3, 4]
解释:

   1            <---
 /   2     3         <---
 \       5     4       <---



拿到这题,一开始的思路是强行遍历右节点,后来发现如果右节点的深度低于左节点时,左节点也是输于右视图的一部分,答案错误。然后参考了相关做法,发现正确的做法应该是层次遍历,判断出每一层的所有内容,然后取最右边的值加入答案。直到最后一个层次遍历完毕。

由于百度到的答案都是使用C++实现的,他们先入左节点再入右节点,C++的队列定义可以取队首或者队尾的内容,这样可以方便取出最右节点。但是JAVA中只能取队首的内容。于是我将右节点先入队,直接取队首,就是答案。

并且,需要注意层次的关系,不要混乱了层次。

代码如下:

 1 class Solution {
 2     List<Integer> ans=new LinkedList<>();
 3     
 4     public List<Integer> rightSideView(TreeNode root) {
 5         Queue<TreeNode> queue=new LinkedList<>();
 6         if(root==null)
 7             return ans;
 8         queue.add(root);
 9         while(!queue.isEmpty())
10         {
11             Queue<TreeNode> quetmp=new LinkedList<>();
12             ans.add(queue.peek().val);
13             while(!queue.isEmpty())
14             {
15                 TreeNode nodetmp=queue.poll();
16                 if(nodetmp.right!=null)
17                     quetmp.add(nodetmp.right);
18                 if(nodetmp.left!=null)
19                     quetmp.add(nodetmp.left);
20             }
21             queue=quetmp;
22         }
23         return ans;
24     }
25    
26 }

 

领扣(LeetCode)二叉树的右视图 个人题解

原文:https://www.cnblogs.com/axiangcoding/p/9965887.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!