力扣hot100二刷——二叉树

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

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

36	⭐⭐⭐	Easy	二叉树	94/二叉树的中序遍历	左-中-右 递归法，当节点不为空时 将节点的左子树传入传入递归函数 添加当前节点到list 将节点的右子树传入传入递归函数 迭代法，维护一个栈，当栈不为空 或 节点不为空时 先遍历左子树，遍历过程中将节点入栈 遍历到空节点后，栈顶元素出栈，再遍历右子树	Deque stack = new ArrayDeque<>();
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 三者中的较大者

图片版：