【LeetCode Hot100】199.二叉树的右视图和56.合并区间
摘要
这篇文章用来记录我在练习 hot100 中题号199和题号56的做题过程。
199. 二叉树的右视图
先来看199题——二叉树的右视图。题目见下图：
第一次思路
我第一次的做题思路是既然我们是要右视图，那么道理很简单，我们就尽量沿着右边的子树右孩子和左边子树的右孩子一直往下深度遍历不就好了？
所以我创建了两个数组lList和rList分别存储左子树和右子树的遍历结果，再比较List大小，rList大，那就直接返回，lList大，就截取lList中超过rList的部分，拼接到rList上。当时自我感觉非常符合右视图，因为我的做法是一直优先找右孩子。
第一次错误题解
我的第一次错误题解见下文：
classSolution{List<Integer>rList=newArrayList<Integer>();List<Integer>lList=newArrayList<Integer>();publicList<Integer>rightSideView(TreeNoderoot){if(root==null){returnnewArrayList<Integer>();}//保存右遍历结果rList.add(root.val);//保存左遍历结果lList.add(root.val);ldfs(root.left);rdfs(root.right);if(rList.size()>=lList.size()){returnrList;}else{for(inti=rList.size();i<lList.size();i++){rList.add(lList.get(i));}returnrList;}}//优先找左子树的右孩子publicvoidldfs(TreeNoderoot){if(root!=null){lList.add(root.val);//只要右孩子不为空就走右孩子if(root.right!=null){ldfs(root.right);}else{ldfs(root.left);}}}//优先找右子树的右孩子publicvoidrdfs(TreeNoderoot){if(root!=null){rList.add(root.val);//只要右孩子不为空就走右孩子if(root.right!=null){rdfs(root.right);}else{rdfs(root.left);}}}}测试结果与反例
这个做法在进行简单的运行测试的时候成功通过，在最后提交时判错。因为测试用例正巧碰上了当前思路的巧合：整个左右子树都是右孩子多于或等于左孩子，或者是右孩子没有只能找左孩子。我们来看几个巧合：
图1：2子树只有右孩子
图2：2子树只有左孩子但是没有右孩子
那不满足巧合的呢？
很明显，我们策略是右孩子不为空就走右孩子，那走到节点2，就去节点5了。哎嘿，没错，到这里结束了。。。下面右视图也能看到的6节点和7节点根本没走到，所以这个做法是错的。
正确做法
那我们再来看看正确的做法，也是一样的思想，优先找右边的孩子。但这次不是走右孩子之后，左孩子不管了。简要的思路还是使用深度遍历，在遍历过程中维护一个深度变量depth，当我们找到同一层节点最右边的孩子时，保存到结果List中同时深度变量depth加1，此时深度遍历同一层其他孩子那里时，发现depth== List.size(); 时，说明在这一层中，右视图能看到的节点已经找到了，这个节点就不用保存了，我们继续往下走就可以了。
代码参考：
class Solution { List<Integer> ans = new ArrayList<>(); public List<Integer> rightSideView(TreeNode root) { dfs(root, 0); return ans; } public void dfs(TreeNode root, int depth) { if (root == null) { return; } if (depth == ans.size()) { ans.add(root.val); } dfs(root.right, depth + 1); dfs(root.left, depth + 1); } }56. 合并区间
我们再来看第二个题目，56题：合并区间。题目见下图：
思路
在初次看到这个题时，很容易想到那依旧暴力for循环。我们先固定一个区间，然后遍历其他所有区间找到可以合并的。但我们仔细观察就会想到，我们在合并两个区间的时候，往往最先看的是区间A的右边界与区间B的左边界相比，再看区间A的右边界与区间B的右边界相比。那我们是不是可以先把数组按照左边界的大小先排个序呢？这样我们在比较的时候不就只用看相邻两个区间了吗？而且只用看左区间右边界和右区间左边界的关系就好了。
那数组排序呢？我们可以直接用Arrays提供的sort()函数，自定义一下Comparator的比较规则就可以非常简单的实现。
实现代码
按照这个思路，我们就不需要再用for循环从头找到尾，费时费力的解决了，下面看实现代码：
class Solution { public int[][] merge(int[][] intervals) { if(intervals.length == 0){ return new int[0][2]; } Arrays.sort(intervals, new Comparator<int[]>(){ public int compare(int[] interval1,int[] interval2){ //按照左边界做升序排列 return interval1[0] - interval2[0]; } }); //保存最终结果 List<int[]> ans = new ArrayList<int[]>(); for(int i = 0; i < intervals.length; ++i){ //当前区间左边界 int l = intervals[i][0]; //当前区间右边界 int r = intervals[i][1]; // 1.ans中还没有合并后的区间以及不需要合并的区间结果 // 2.当前区间左边界和ans中最新结果的右边界比较，因为当前区间一定排序在ans中已使用过的所有区间的右边 if(ans.size() == 0 || ans.get(ans.size() - 1)[1] < l){ // 1.ans中还没有区间结果 // 2.当前区间不需要进行合并 ans.add(new int[]{l,r}); } //当前区间左边界和ans中最新结果的右边界比较之后发现可以合并 else{ //这里取两个区间的右边界最大值是因为可能出现这种情况 [1,6],[2,3] ans.get(ans.size() - 1)[1] = Math.max(ans.get(ans.size() - 1)[1], r); } } //别忘了题目要求的返回值类型是二维数组 return ans.toArray(new int[ans.size()][]); } }
