12月刷题记录

12月刷题记录 二叉树

• NC72 二叉树的镜像 （前序遍历交换左右子树+递归）
• leetcode 116. 填充每个节点的下一个右侧节点指针 （借助辅助函数传入两个结点）
• leetcode114. 二叉树展开为链表 （后序遍历，左子树移到右子树，原来的右子树接到新的右子树后）
• leetcode 654. 最大二叉树 （前序遍历找出最大值作为根结点+递归）
• leetcode 105. 从前序与中序遍历序列构造二叉树 （前序遍历，先找根结点位置，再递归）
• leetcode 222. 完全二叉树的节点个数 (后序遍历，节点个数=左子树+右子树+1)
• leetcode 652. 寻找重复的子树 （每棵子树转为字符串，用一个hashmap存子树出现次数，linkedlist存重复子树根结点）
• NC13 二叉树的最大深度（后序遍历）
• leetcode 102. 二叉树的层序遍历（用队列存一层结点）
• NC8 二叉树中和为某一值的路径(二) （dfs，用path记录当前的路径）
• NC81 二叉搜索树的第k个节点（二叉搜索树中序遍历刚好是升序结果）
• leetcode538. 把二叉搜索树转换为累加树（改变中序遍历的递归顺序可以得到降序输出 右-根-左）
• leetcode 98. 验证二叉搜索树（输出中序遍历结果，判断是否符合升序）
• leetcode 101. 对称二叉树 （借助辅助函数，传入两个结点进行递归）
• NC62 判断是不是平衡二叉树 （递归计算每个结点的高度，并计算左右子树的高度差，用bool记录是否平衡）
• NC11 将升序数组转化为平衡二叉搜索树（二分法找中间元素作为根结点再递归左右子树）
• NC9 二叉树中和为某一值的路径(一) （前序遍历）
• NC60 判断一棵二叉树是否为搜索二叉树和完全二叉树 （搜索二叉树：中序遍历后得到的是升序，完全二叉树：层序遍历，遇到不同时拥有左右儿子的结点以后，出队的所有结点都是叶结点。且不会出现只有右儿子的结点）
• NC136 输出二叉树的右视图（）
• NC117 合并二叉树 （把第二棵树每个结点上的值加到第一棵树，base case是两棵树中存在空节点时）
• NC6 二叉树中的最大路径和（后序遍历，递归计算最大贡献值，再计算最大路径和）
• NC14 按之字形顺序打印二叉树（层序遍历+判断奇偶层）
• NC5 二叉树根节点到叶子节点的所有路径和 （sum=presum*10+root.val）

递归

• NC26 括号生成（递归，记录左括号和右括号剩余的个数）

栈

• 有效括号序列（左括号入栈，右括号出栈）

DFS

• 岛屿数量（dfs，发现岛屿就把相邻岛屿都淹没，岛屿数+1）

动态规划

• NC126 兑换零钱(一)
• NC7 买卖股票的最好时机(一) （第i天是否卖出）
• NC163 最长上升子序列(一) （dp[i]定义为以arr[i]为结尾，最长上升子序列的长度）
• NC165 最长公共子序列(一) （二维dp）
• NC92最长公共子序列(二) （利用上一题生成好的dp倒退回去）
• NC153 信封嵌套问题 （对w升序，w相同则h降序，再对h进行NC163的 *** 作）
• NC19 连续子数组的最大和（dp[i]定义为以array[0]为结尾的连续子数组）
• NC154 最长回文子序列（二维dp）