力扣hot100二刷—

力扣hot100二刷——二叉树

第二次刷题不在idea写代码，而是直接在leetcode网站上写，“逼”自己掌握常用的函数。

标志	掌握程度	解释	办法
⭐	Fully 完全掌握	看到题目就有思路，编程也很流利
⭐⭐	Basically 基本掌握	需要稍作思考，或者看到提示方法后能解答
⭐⭐⭐	Slightly 稍微掌握	需要看之前写过的代码才能想起怎么做	多做
⭐⭐⭐⭐	absolutely no 完全没有掌握	需要看题解才知道怎么做	背
⭐⭐⭐⭐⭐	有难度的高频题	需要看题解才知道怎么做，而且过几天就忘了这道题怎么做了	背背

36	⭐⭐⭐	Easy	二叉树	94/二叉树的中序遍历	左-中-右递归法，当节点不为空时将节点的左子树传入传入递归函数添加当前节点到list 将节点的右子树传入传入递归函数迭代法，维护一个栈，当栈不为空或节点不为空时先遍历左子树，遍历过程中将节点入栈遍历到空节点后，栈顶元素出栈，再遍历右子树
37	⭐⭐⭐	Easy	二叉树	104/二叉树的最大深度	递归法，遇到空节点返回0 将节点的左子树传入传入递归函数，并将返回值 +1 将节点的右子树传入传入递归函数，并将返回值 +1 返回两者中较大者 return Math.max(maxDepth(root.left) + 1, maxDepth(root.right) + 1);
38	⭐⭐⭐	Easy	二叉树	226/反转二叉树	递归法，遇到空节点直接返回交换当前节点的左右子树将节点的左子树传入传入递归函数将节点的右子树传入传入递归函数
39	⭐⭐⭐	Easy	二叉树	101/对称二叉树	递归法，递归函数的输入分别为左子树的节点和右子树的节点两节点均为空，return true 一节点为空，另一节点不为空，return false 两节点均不为空，但值不同，return false 两节点均不为空，值相同，比较left.left 和 right.right，left.right 和 right.left，返回两个结果的与
40	⭐⭐⭐	Easy	二叉树	543/二叉树的直径	递归法，分别计算当前节点的左右子树的深度更新目前深度最大值ans：左子树深度+右子树深度和 ans 比较返回的是左子树深度和右子树深度的较大者，而不是当目前深度的最大值
41	★★★★	Medium	二叉树	102/二叉树的层序遍历	关键在于：找到一个可以标志某层节点的变量，要么是层数，要么是某层的节点个数层数递归法，递归函数的输入参数：1.当前节点 2.当前层数当前节点为空，直接返回层数++ 如果当前ansList的长度 < 当前层数，说明是第一次遍历到该层，要创建一个itemList加入到 list 将当前节点加入到 ansList中对应层数位置的itemList中将当前节点的左子树传入传入递归函数将当前节点的右子树传入传入递归函数队列迭代法，维护一个队列来遍历每层元素首先将root根节点存入队列开始遍历二叉树，队列为空则跳出循环维护length记录该层的节点个数如果当前length > 0，则移除队头节点，将节点值加入到 item 集合中，并移入该节点的左右子节点（如果不为空的话），并且length-- length == 0 则将item 加入list
42	★★★★	Easy	二叉树	108/将有序数组转换为二叉搜索树	递归法，核心思想：不断分割数组，数组中间位置的值一定最适合作为当前的根节点递归参数：数组、左边界、右边界当左边界 ≤ 右边界时，求中间索引，把数组中间索引的值作为新的节点令节点的左右子节点分别为下一轮递归返回的节点返回当前节点如果左边界＞右边界，直接返回空节点。
43	★★★★	Medium	二叉树	98/验证二叉搜索树	递归法，验证二叉搜索树就是看这棵树的中序遍历的序列是否是严格递增的。维护一个pre节点来保存上一个节点，用来和当前节点比较，初始设为null，当pre != null时再比较当前节点为空时直接返回true 将节点的左子节点传入传入递归函数比较当前节点和上个节点的大小，当前节点 ≤ 上个节点则return fasle 节点的右子节点传入传入递归函数返回左子树和右子树验证结果的与操作
44	★	Medium	二叉树	230/二叉搜索树中第k小的元素	和上题的思路是一样的，二叉搜索树的中序遍历是严格递增的，中序遍历二叉树的第k个节点即为要找的答案巧妙定义类变量，即可用一句话找到结果 if(–k == 0) ans = root.val;
45	★	Medium	二叉树	199/二叉树的右视图	层数递归法：层数从0开始右中左递归遍历二叉树，List<List> list 维护一个集合来存放每一层的值递归结束后，统计每层的第一个元素的集合即为答案
46	⭐⭐⭐	Medium	二叉树	114/二叉树展开为链表	反先序递归遍历：右左中反先序递归遍历二叉树，从最后往最前依次完成链表每次遍历，要更新nextNode，也就是下一个节点
47	★★★★	Medium	二叉树	105/从前序与中序遍历序列构造二叉树	递归遍历，3个递归参数为preorder中当前头结点的索引、inorder中当前子树的左右边界索引由前序遍历得到头节点，在inorder中搜索头节点，为了方便搜索，维护一个map来存放inorder的值和对应的索引根据inorder中的头节点，将inorder划分为左右子树，并将左右子树的边界分别传入递归函数要注意右子树的递归函数略微复杂： node.right = buildTree1(root + mid - left + 1, mid + 1, right);
48	⭐⭐⭐	Medium	二叉树	437/路经总和III	前序遍历+前缀和注意，sum和map中的键都应该是long型。由根节点从上至下前序遍历并更新sum，每次遍历先检查map中是否包含sum - target并更新ans 将当前和在map中的次数更新将当前节点的左子节点传入递归函数，将当前节点的右子节点传入递归函数将当前遍历层的sum在map中的次数 - 1 将当前sum 减去当前节点的值。
49	★★★★	Medium	二叉树	236/二叉树的最近公共祖先	搞明白一件事情：只要碰到一个节点（不管是p还是q）就返回当前节点，不用再遍历下面的节点了结束递归的条件：root == null \|\| root == p \|\| root == q 对于当前节点，如果只有一个子树返回值不为空，另一个子树返回值为空，说明另一个节点要么也在该子树下面，他们的共同祖先就是返回的节点；要么在其他节点下，不管怎么样都不用遍历剩下的节点。
50	★★	Hard	二叉树	124/二叉树的最大路径和	后序遍历递归结束条件，空节点返回0 当前节点的左子节点和右子节点分别传入递归函数，返回结果分别为左右子树的最大路径和更新当前最大值 ans = Math.max(ans, leftMax + rightMax + root.val); 返回值：当前节点+左子树最大路径和、当前节点+右子树最大路径和、0 三者中的较大者