【LeetCode Hot100】199.二叉树的右视图和56.合并区间摘要这篇文章用来记录我在练习 hot100 中题号199和题号56的做题过程。199. 二叉树的右视图先来看199题——二叉树的右视图。题目见下图第一次思路我第一次的做题思路是既然我们是要右视图那么道理很简单我们就尽量沿着右边的子树右孩子和左边子树的右孩子一直往下深度遍历不就好了所以我创建了两个数组lList和rList分别存储左子树和右子树的遍历结果再比较List大小rList大那就直接返回lList大就截取lList中超过rList的部分拼接到rList上。当时自我感觉非常符合右视图因为我的做法是一直优先找右孩子。第一次错误题解我的第一次错误题解见下文classSolution{ListIntegerrListnewArrayListInteger();ListIntegerlListnewArrayListInteger();publicListIntegerrightSideView(TreeNoderoot){if(rootnull){returnnewArrayListInteger();}//保存右遍历结果rList.add(root.val);//保存左遍历结果lList.add(root.val);ldfs(root.left);rdfs(root.right);if(rList.size()lList.size()){returnrList;}else{for(intirList.size();ilList.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);}}}}测试结果与反例这个做法在进行简单的运行测试的时候成功通过在最后提交时判错。因为测试用例正巧碰上了当前思路的巧合整个左右子树都是右孩子多于或等于左孩子或者是右孩子没有只能找左孩子。我们来看几个巧合图12子树只有右孩子图22子树只有左孩子但是没有右孩子那不满足巧合的呢很明显我们策略是右孩子不为空就走右孩子那走到节点2就去节点5了。哎嘿没错到这里结束了。。。下面右视图也能看到的6节点和7节点根本没走到所以这个做法是错的。正确做法那我们再来看看正确的做法也是一样的思想优先找右边的孩子。但这次不是走右孩子之后左孩子不管了。简要的思路还是使用深度遍历在遍历过程中维护一个深度变量depth当我们找到同一层节点最右边的孩子时保存到结果List中同时深度变量depth加1此时深度遍历同一层其他孩子那里时发现depth List.size(); 时说明在这一层中右视图能看到的节点已经找到了这个节点就不用保存了我们继续往下走就可以了。代码参考class Solution { ListInteger ans new ArrayList(); public ListInteger 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 Comparatorint[](){ public int compare(int[] interval1,int[] interval2){ //按照左边界做升序排列 return interval1[0] - interval2[0]; } }); //保存最终结果 Listint[] ans new ArrayListint[](); 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()][]); } }