第二次刷题不在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 三者中的较大者 |
图片版: