因为最近的拖拉，生生把计划每天的刷题改成了两天一刷，所以今天多做几道吧。
二叉树最大深度
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
image.png
先说题外话，这个力扣的题应该是有规律的吧，连着好几道题都是二叉树的了。其实这种题我个人的思路首先考虑递归，然后尤其是这种深度肯定要遍历的，不递归怎么处理呢？上道题倒是扩展了一个思路那就是队列，但关键上我对队列一点都不熟啊。
递归是大体思路，但是具体怎么递归是个问题。反正我个人只能是抽丝剥茧的考虑，然后不断的尝试运行，我习惯用eclipse把代码下上断点一遍遍来回跑。其实正常来讲递归走三四次就能看出到底是不是对的了。
回归这到底，其实很简单的，首先一个节点有左右两个节点，正常判断不管是左有还是右有甚至左右都有，但是深度应该只加1的。当然如果都没有深度不加。如果这个节点是空节点，那么直接不用管子节点了，深度也是0（因为我写的其实很墨迹。甚至还用了静态变量，各种条件啥的，最后看了题解发现就是一行代码的事！）
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int maxDepth(TreeNode root) {
return root==null?0:Math.max(maxDepth(root.left),maxDepth(root.right))+1;
}
}
真的，我只能说这个答案的作者真的真的厉害，反正我之前是要判断，判断自己空不空，左右空不空，最少有一个不空是1.不然是0反正乱的不行，然后我用了个三元运算，结果是超时。真的是想法设法运行n次都不对，但是看了人家的代码，一行搞定。逻辑很清晰属于那种一看就会的。然后自己写反正是写不出来。
然后这道题因为其实属于一个弯儿，想不通卡死了，想通了直接通关了。其实我觉得递归差不多就是这样的，找到那个点通关，点找错了莫名其妙什么bug都有。但是对于为什么三元运算就超时，Math.max就可以我到现在也不太明白。然后这道题就这么过吧。下一道
二叉树的层次遍历II
题目：给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
题目
思路：因为我也才审题还没做，但是简单的想法：之前我就说了关于二叉树的遍历递归是一种习惯性的思维，至于这个题的从上往下还是从下往上不过是顺序问题。实在不行不怕性能问题还能自己调整顺序呢对吧。所以开始撸代码：
撸完回来了，只能说天道好轮回，上上一道题的迭代方法我不好好看，这道题报应来了。其实可以用102题的解法，就像我说的先正序得出结果，然后用这个结果集反转，就ok了，然后做完屁颠屁颠去看了题解，原来这道题的意思是不让用反转。。不过解决办法就是每次插入时放在第一个元素的位置。但是因为这个其实和上一道题大同小异，所以想了想还是决定去看看迭代法。其实除了一个不熟悉的数据结构Queue，剩下也不是多难解。
Queue
我想了想还是单独把Queue提出来，简单的说两句，也算是我自己的复习和熟悉了解。
首先基本上，一个队列就是一个先入先出的数据结构。
常用的类关系图
其中常用的方法：
- add 增加一个元索 如果队列已满，则抛出一个IIIegaISlabEepeplian异常
- remove 移除并返回队列头部的元素 如果队列为空，则抛出一个NoSuchElementException异常
- element 返回队列头部的元素 如果队列为空，则抛出一个NoSuchElementException异常
- offer 添加一个元素并返回true 如果队列已满，则返回false
- poll 移除并返问队列头部的元素 如果队列为空，则返回null
- peek 返回队列头部的元素 如果队列为空，则返回null
- put 添加一个元素 如果队列满，则阻塞
- take 移除并返回队列头部的元素 如果队列为空，则阻塞
回归到本题，其实我主要想介绍和复习的就是这几个方法的使用。本题中用到的就是add和poll。一个的添加元素，一个是移除并获取元素。（本题不涉及队列满）
然后代码的思路也很简单：首先将跟节点放到队列中。然后在队列不为空的情况下遍历队列，将当前节点另存一个list中（因为树是有层 的，所以遍历出来的也只是一层树）。如果当前节点还有左右节点也放到队列中。又因为之前遍历的时候已经确定取出来的元素数量了。所以新添加的元素不会被拿出来。
这一遍遍历完了，该层节点都取出来放到list中了，再将整个list放到结果集中，并且放到第一个元素的位置。
再往下下一层循环，此时队列中的元素就是下一层元素了。还是从左到右怎么放进去的怎么拿出来存到list里。同时把再下一层的叶元素存到队列中。把list放到结果集的第一个元素的位置。这样一次次循环，每次都把下面的元素放到前面的位置。最后queue为空说明下一层子元素没有了！也就退出了循环，此时得到的结果集就是想要的结果集。无论是数据还是顺序都是题目要求的。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
LinkedList<List<Integer>> result = new LinkedList<List<Integer>>();
if(root==null){
return result;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
//当队列为空才跳出循环
while(!queue.isEmpty()){
//这个list是每一层的元素集
List<Integer> list = new ArrayList<Integer>();
//每次取出一层的数据
int count = queue.size();
//因为在这已经确定了取出元素的个数，所以循环中再往队列中放置元素也不怕被取出来。
for(int i =0;i<count;i++){
//取出元素的同时移除元素
TreeNode node = queue.poll();
list.add(node.val);
//如果下一层有数据则放到队列中
if(node.left!=null){
queue.add(node.left);
}
if(node.right!=null){
queue.add(node.right);
}
}
//每次都放在结果集的第一个元素的位置，这样下层放在前符合题意
result.addFirst(list);
}
return result;
}
}
注意上文用的LinkedList是因为只有这个才有addFirst方法。因为我之前看题解都有这个addFirst，然后我用了报错，特意搜索了这个方法，仅仅是LinkedList才有。并且我做了一个实验，用List来运行，正常追加，最后反转居然比用LinkedList的性能要好。但是因为说是不要反转，所以我这里还是用的LinkedList。
将有序数组转化为二叉搜索树
题目：将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
题目
思路：说一下我的思路，因为是平衡树，所以排序后总个数单数的话根节点是中间位数，总个数是双数的话中位数有俩，因为二叉树一般以左为主，所以我选择中间两位的后一个（这样保证左节点有右节点没有）。所以我这里就用这种方式一个个判断。然后老生常谈，二叉树要么迭代要么递归。我这里打算用递归的方法。
直接上代码：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
int len = nums.length;
if(len==0){
return null;
}
if(len==1){
//如果这个数组长度等于1说明数组中只有一个元素，直接就是叶节点了，不用往下判断了。
return new TreeNode(nums[0]);
}
int root = 0;
if(nums.length%2==0){
//这里是如果正好是偶数，总中位数是俩，然后这里是取了后面的那个。正常应该+1。但是因为这里的是第几个元素，要换成下标的话应该还要减一。所以这里不加也不减。
root = nums.length/2;
}else{
//这里正常是+1，然后除二的结果是第几个元素，然后再-1才是元素的下标。这里直接—1是简化后的写法
root = (nums.length-1)/2;
}
//确定下标为root的数为根节点
TreeNode tree = new TreeNode(nums[root]);
//再将整个数组拆分成左右两个子数组
int[] left = new int[root];
for(int i =0;i<root;i++){
left[i]=nums[i];
}
//左数组中间值挂到左叶上，右边挂到右叶上，直到没有元素挂则退出递归
tree.left =sortedArrayToBST(left);
//判断后面还有没有元素了
if((len-root)==1){
//说明后面没有元素了，不用找右节点了，直接返回
return tree;
}
//这里应该是数组的长度减去到root的元素数。因为root是下标，从0开始，所以还要额外减一
int[] right = new int[len-root-1];
//用来作为右数组的下标
int j = 0;
//第一个元素从root后开始算，所以起始就是root+1
for(int i=root+1;i<len;i++){
right[j] = nums[i];
j++;
}
tree.right =sortedArrayToBST(right);
return tree;
}
}
怎么说呢，该有的解释我在注解里写的很清楚了。从第一次提交成功到一次次修改想要性能和执行时间更优差不多五六个版本，然后性能越运行越低上哪说理去？我要直视和大神的差距，并且认真的去分析，看人家的思路了。
很好，我看完大神的思路回来了，只能说思路差不多的思路，但是代码的精巧性完全不能比。下面是代码：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return buildTree(nums,0,nums.length-1);
}
//参数是数组，左下标，右下标
public TreeNode buildTree(int[] nums,int l,int r){
if(l>r){
return null;
}
//中位数
int m = l+(r-l)/2;
TreeNode tree = new TreeNode(nums[m]);
tree.left = buildTree(nums,l,m-1);
tree.right = buildTree(nums,m+1,r);
return tree;
}
}
我觉得我最麻烦的部分就是把数组不断的拆分成小数组，然后浪费性能占用数组空间，而这个解题的思维根本就没拆分小数组，直接在原数组中定位节点下标了。但是虽然速度上来了，性能却比我的低。只能说读懂的情况下代码比较优雅？反正这道题我自己挺满意自己的，哈哈
这篇文章就写到这，如果帮助到你了记得点个喜欢点个关注呦~也祝大家工作顺顺利利！
网友评论