刷题打卡贴-死磕秋招

5.14+5.15 CC189第二章 linkedlist 8道题 完成

回归地里面的打卡贴
最近一个月和其它3个小伙伴一起开了一个google doc相互监督刷题进度，就没有怎么来地里做总结。 现在基本做完了所有的Tree 的题目以及小半部分的DP的题目，开一个阶段总结贴梳理一下Tree的知识点
参考总结 ：
Tree总结1

1. 先是最基础的Tree的遍历，包括前序(preorder), 中序(inorder), 后序(postorder)，Tree的遍历是后面的进阶题的基础，因为遍历的过程中可以同时对Tree的每个节点做一些额外的操作例如 加和，比较，变换位置等等
递归版本的遍历十分简单，只需要注意必须是边走边加即可，需要单独开一个helper(TreeNode root, List<Integer> res) function使用递归来做处理
非递归的版本的遍历，难度依次增加，最简单的是Preorder:
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
   TreeNode node = stack.pop();
   res.add(node.val);
   if (node.right != null) {
     stack.push(node.right);
   }
   if (node.left != null) {
     stack.push(node.left);
   }

下一难度的是inorder traversal， 有一个小的trick是在遍历到左下的节点时，要有一步check右节点操作，如果右子节点存在左子树，那么要继续遍历左子树, 如果没有右子节点，那么该节点就直接作为第一个输出的节点即可，将其加入到最后的res List当中并向上返回。用一个两个限定条件的while loop来完成这件事

1. while (!stack.isEmpty() || head != null) {
   
2.    if (head != null) {
   
3.      stack.push(head);
   
4.      head = head.left;
   
5.    } else {
   
6.      head = stack.pop();
   
7.      res.add(head);
   
8.      head = head.right;
   
9.    }
   

复制代码

最后是最难的postorder 遍历
有两种实现方法，分别使用了两个栈和一个栈，先说使用两个栈的方法，最基本的思路是一个栈做最简单的preorder,另一个栈负责将preorder的结果倒序

1. //postorder-two stack
   
2. Stack<TreeNode> s1 = new Stack<TreeNode>();
   
3. Stack<TreeNode> s2 = new Stack<TreeNode>();
   
4. s1.push(head);
   
5. while (!s1.isEmpty()) {
   
6.    head = s1.pop();
   
7.    s2.push(head);
   
8. //注意这个地方顺序与preorder相反，因为s2会倒序，所以这里是先加node.left再加node.right，而preorder是先加node.right, 再加node.left
   
9.    if (head.left != null) {
   
10.      s1.push(head.left);
    
11.    }
    
12.    if (head.right != null) {
    
13.      s1.push(head.right);
    
14.    }
    
15. }
    
16. while(!s2.isEmpty()) {
    
17.    res.add(s2.pop());
    
18. }

复制代码

下面是使用一个栈来实现postorder,其中的head指针表示最近一次弹出并加入到res List当中的节点，curr表示的是stack的栈顶节点，也就是当前可能马上要打印的节点，先走左，不行再走右，还不行就打印curr， top down的走法

1. //postorder-one stack
   
2. if (head != null) {
   
3.    Stack<TreeNode> stack = new Stack<TreeNode>();
   
4.    stack.push(head);
   
5.    TreeNode curr = null;
   
6.    while (!stack.isEmpty()) {
   
7.      curr = stack.peek();
   
8.      if (curr.left != null && head != curr.left && head != curr.right) {
   
9.        stack.push(curr.left);
   
10.      } else if (curr.right != null && head != curr.right) {
    
11.        stack.push(curr.right);
    
12.      } else {
    
13.        res.add(stack.pop());
    
14.        head = curr;
    
15.       }
    
16.    }
    
17. }

复制代码

有了Tree的遍历做基础，来看几道用遍历+节点操作就可以秒杀的题目：
Inorder 可以和BST的特性结合来构造有序的数组
297. Serialize and Deserialize Binary Tree 直接一个Preorder + Queue数据结构记录节点，注意对空节点的处理 "#"
538. Convert BST to Greater Tree 直接声明一个全局变量sum来记录当前走过的所有greater node的sum + 一个右中左的中序遍历即可
617. Merge Two Binary Trees 4种情况分类讨论即可： 1. t1 == null && t2 == null 2.t1 == null 3.t2 == null 4.t1 != null && t2 != null
108. Convert Sorted Array to Binary Search Tree 直接一个Inorder + 数组二分 注意递归的helper function 终点 if (start > end) return null;
230. Kth Smallest Element in a BST 设全局变量，直接Inorder 遍历解决
814. Binary Tree Pruning 类似于postorder 的处理手法,左右中 prune的条件是(root.left == null && root.right == null && root.val == 0)
有点小难度的遍历类题目：
106. Construct Bianry Tree from Inorder and Postorder Traversal
105. Construct Binary Tree from Preorder and Inorder Traversal
这两道题的相似性在于使用Preorder 和 Postorder 数组来构造树的节点，利用inorder来确定每棵树的范围
173. Binary Search Tree Iterator
285. Inorder Successor in BST
这两道题本质上是同一道题，都是求BST的inorder 的下一个节点，可以用两个指针 或者辅助栈来做。如果用双指针，则声明一个新的pre指针来记录当前位置的父节点，先遍历到最左下作为起点，然后找后继节点需要分类讨论，如果当前节点位于pre节点的左边，那么当前节点的right subtree会存在后继，如果不存在right subtree,那么当前节点的parent节点就可以直接作为后继节点。


Divide & Conquer 思路
687. Longest Univalue Path 分别先算Left 和 right 的深度，如果root.val == val -> Math.max(left, right) + 1; else return 0 有一个Trick的地方是在helper()的递归function当中，有一个三级结构的存在helper 当中的val是父节点的value, 向下传递的是当前节点的root.val, left = helper(root.left, root.val) , 而得到的left/right 结果是下面子节点的返回结果
543. Diameter of Binary Tree 687的简化版，不需要判断root.val == val直接做加减
669. Trim a Binary Search Tree 判断落点位置，root.val < L, 往右走（右子树都大于root), > L && < R (保留当前节点 root.left = Trim(root.left, L, R), root.right = Trim(root.right, L, R),  > R, 往左走
112. Path Sum  是否存在root-> left的路径 == 只需要找到一条路径即可，递归的function只需要保证每次都减掉当前的root.val即可
113. Path Sum II 同样是找root-> left的路径，但是需要打印所有的路径，所以是一个exhuastive search 需要用到回溯的算法，每个节点都是潜在的添加值，所以每个节点都应当添加到curr当前路径当中，但是只有符合出口要求的curr路径才能被添加到res总的路径list当中 helper(TreeNode root, List<List<Integer>> res, List<Integer> curr, int sum)
437. Path Sum III 每一个TreeNode 节点都可以成为一个path的起点，写helper() 返回的是以这个点作为起点的path数量，那么对于每个点分别要有3个helper() 对应以当前点位起点，当前点的left节点，当前点的right节点
101. Symmetric Tree
100. Same Tree
110. Balanced Binary Tree 用ResultType 包装类来分别存depth + isBalanced 两个变量
226. Invert Binary Tree 左换右， 右换左，注意用temp变量来暂时存一下
236. LCA of Binary Tree 何时退出找到就退出，可能是Left, 也可能是root, 也可能是right, 判断上下级关系
257. Binary Tree Paths 操作的时候要考虑四种情况if(root == null) if (currPath == "") else{...} if (root.left == null && root.right == null)
Path 类型的题目：
全局最大是一定要考虑当前root.val + left + right, 但是function本身返回的应该是左或右两支中较大的一支
TOP-> DOWN  BOTTOM -> UP 都有可能，根据递归与操作的出现顺序的前后来调整 先递归 再操作是bottom-up, 先操作再递归是top-down

Level Order 遍历思路 注意while(!queue.isEmpty()) 是对于整个树的多个level遍历，for(int i = 0; i < size; i++) 是对当前的一个level的处理
637. Average of Levels in Binary Tree 注意使用double 数据类型，因为会存在小数
515. Find Largest Value in Each Tree Row
513. Find Bottom Left Tree Value 一个逆序的level order直接解决
199. Binary Tree Right Side View 记录每一层的最右边的节点
116. Populating Next Right Pointers in Each Node 设置一个pre节点来指向左边的节点，每次pop()出来的节点作为当前的节点pre.next指向当前节点


小Trick 题：
222. Count Complete Tree Nodes 根据完全二叉树的性质使用位运算来加快速度

待补充：
链表 + Tree
DP + Tree

6.14
重做
463. Island Perimeter
733. Flood Fill
695. Max Area of Island
200. Number of Island
Union Find内容复习
quick Find算法 find: return id[p] union: find(p) find(q) for loop遍历整个id去调整id[i] == pID的节点
quick Union算法 find: while(p != id[p]) p = id[p]; 直到找到根触点停止find()操作， union: pRoot = find(p); qRoot = find(q); if(pRoot == qRoot) return; id[pRoot] = qRoot;
加权quick-Union算法: 在union过程中添加树的大小比较 if(size[i] < size[j]) { id[i] = j; size[j] += size[i];} else: {id[j] = i; size[i] += size[j];}

6.15
752. Open the Lock
743. Network Delay Time
417. Pacific Atlantic Water Flow
BFS + 最短路径
6.16
Dijkstra 算法梳理
Dijkstra是由一个单一的源点出发，计算整个联通分享之中与之相连元素的最短路径算法。算法的实现需要维护一个minHeap来记录当前的最短路径，通过比较res[i] 与 res[node] + grid[node][i](weight) 来更新res中的各个节点最短距离。

6.17
重做
752. Open the Lock
743. Network Delay Time
417. Pacific Atlantic Water Flow
PriorityQueue的实现，Princeton《算法》教材2.4节，感受到了数据结构的威力，之前在实现Dijkstra算法中使用到了PriorityQueue, 但是没有太多深入实现的部分，仔细研究之后发现PriorityQueue可以使用最简单的数组来实现(借助于完全二叉树的特性），同时由于堆结构自身的特性(root 为最小节点，且每一个root都小于自己的child节点) 保证了插入和删除操作的时间复杂度都是LogN(N为待处理的元素总数）。注意实现的过程不是直觉性的将每个新的输入和已知的M个最大的元素作比较，因为这样作比较的代价很高。
k: 当前节点
k/2: 当前节点的父节点
2k or 2k + 1: 当前节点的子节点
而是利用堆的整体特性，
insert()操作将元素添加到最底层： 并使用swim()操作将新插入的节点上浮到一个适当的位置
private void swim(int k) {
  while(k > 1 && less(k / 2, k)) {
    exch(k / 2, k);
    k = k / 2;
  }
}
delete()操作将元素从根节点删除并交换最底层最后一个节点到根节点 + sink() 操作
private void sink(int k) {
  while (2 * k <= N) {
    int j = 2 * k;
    if (j < N && less(j, j + 1)) j++; // change the larger element
    if (!less(k, j)) break;
    exch(k, j);
    k = j; //update the pointer
  }
}

6.6
重做：725. Split Linked List in Parts
23. Merge k Sorted Lists
25. Reverse Nodes in k-Group
143. Reorder List
328. Odd Even Linked List
100. Same Tree
101. Symmetric Tree
538. Convert BST to Greater Tree
572. Subtree of Another Tree
其中 bugfree: Odd Even Linked List, Same Tree
剩余4题全部出现了小问题：包括了笔误：笔误 curr.next = prev; 小的typo  val 少敲了一个l 写错成va, 数组的初始化写成 ListNode(k)
出现以前不会犯过的错误的主要原因是1.心态急躁，追求速度，因为这些题都是至少做过3次都没有bugfree的题，心里想着这次一定能够bugfree，于是在写代码的过程之中只关注了上一次或上两次犯过的错误不要重犯，而忽视了其它的细节。 2.基础不够扎实，对于java的语法不够熟练，比如数组初始化写成ListNode(k)就是一个十分典型的例子，这种小的typo如果足够敏感是可以在写题的过程中直接发现的甚至是完全不可能出现的。
总结： 对于多次反复练习过的没有bugfree的题目要更加谨慎的对待，反复做错的题目不能只记 一个思路，更要保证每一个细节都是十分熟悉和确定的。

6.7 LeetCode Tree + Easy Tag filter
101. Symmetric Tree
538. Convert BST to Greater Tree
572. Subtree of Another Tree

144. Binary Tree Preorder Traversal
94. Binary Tree Inorder Traversal
lint448. Inorder Successor in BST
236. Lowest Common Ancestor of a Binary Tree
235. Lowest Common Ancestor of a Binary Search Tree
543. Diameter of Binary Tree
其中bug free:  101. Symmetric Tree 538. Convert BST to Greater Tree 94. Binary Tree Inorder Traversal
对于树的easy题目，做了大概10道题，都是3个月前做过的题目，发现一半多之前能够bugfree的题目现在不能够做到bugfree了， 这就说明了没有及时复习导致了一定程度的遗忘以及对于递归的理解不够深入，之前bugfree可能也仅仅是把答案背下来默写上去的而已。下一步先将easy的题目整理总结，并考虑寻找一些树的题目的模板以及递归的模板来强化练习一下对于递归的理解，最后能够做到写出来的每一个递归程序都能够在头脑中构建出其执行的顺序以及由一个思路来反向构建一个递归程序的水平。

5.16 leetcode 155 21 331 + cc189 chapter3

完成Princeton Alogrithm PartII week1 lecture + SDC nanodegree p5 知识点梳理

5.22
160. Intersection of Two Linked Lists
155. Min Stack
20. Valid Parentheses
331. Verify Preorder Serialization of a Binary Tree
重做

5.23
重做
42. Trapping Rain Water
224. Basic Calculator
402. Remove K Digits
新题
225. Implement Stack using Queues
739. Daily Temperatures
735. Asterodi Collision
316. Remove Duplicate Letters

5.24
复习巩固stack类型的题目
42. Trapping Rain Water
402. Remove K Digits
239. Sliding Window Maximum
739. Daily Temperatures
735. Asterodi Collision
316. Remove Duplicate Letters

给楼主加油！！！

5.25 昨天出门在外忙活买车的事情，搁置了刷题
5.26 重新做
42. Trapping Rain Water
224. Basic Calculator
402. Remove K Digits
225. Implement Stack using Queues
739. Daily Temperatures
735. Asterodi Collision
316. Remove Duplicate Letters
232. Implement Queue using Stacks：
几点总结：
1. stack类型的题目 关键点在于想清楚stack里面要存什么？ 什么时候push()? 什么时候pop()?  因为栈结构的作用在于调整数据的顺序，从后向前依次进行一些处理，最常见的就是括号的优先级（例如：valid parenthesis, basic calculator, decode strings)以及数据的比较(例如daily temperatures, Remove k digits, trapping water) 基本的stack相关实现类题目(implement queue using stacks, Min stack)
2. push() 的元素是满足何种条件下的元素，还是全部的元素都先添加到stack当中，然后在pop()的过程中利用if 条件进行相关的筛选
3. stack 还会结合其他的相关数据结构，例如tree, array等，后期的难题可能需要综合考虑多种数据结构的特点，暂时跳过

同刷题！！！一起加油~

给你们加油