[LeetCode]为什么要LC，从树开始
系列前言:
印象中去年的春节期间，做了一个Rethink专题系列，梳理了NLP的基本技术，尤记得从无锡东站的KFC开始，读一份基于Keras的seq2seq的code，冰镇可乐是真的好喝。2020年的春节，于是有了这个围绕LC的专题，姑且算是笔记。
一般情况下，密集的做LC的题目是面试找工作前开始的，说来尴尬，自己还真没有用心的做过，直到春节前看到组里一位同学的做题记录，加之年底内心疲劳，想着换一换脑子，于是就决定做这个专题。
有啥好处？
（1）考察基本的数据结构和算法思想。对于个人而言，这些基本内容虽然在日常工作中可能一直用到，但是当以工具的方式使用的时候，对我而言，和没用没啥区别，时间久了，自然陌生。
（2）从格外长的独特的2020年春节的做题经历来看，的确是好东西，也是非常的有趣啊，能够解决的问题也是非常的现实，很硬核。过去由于自己没想明白为啥要做这些题，因此心存偏见，觉得意义不大。但是做了好多之后会发现，合理使用数据结构和算法，哪有那么容易？虽然对于专业的ACMer来说，就是刷题，既然是刷题，就是掌握套路。实际上，个人不是很喜欢这种说法。给定问题，不看答案，自己想，还是有难度的，也很锻炼思维。
（3）不能拉组织的后腿。组里的两位同学，一位每周都会做一些，另一位从研究生期间就花了很多时间做LC，可能近年来的研究生同学多是做DL的相关比赛了吧，比如我们组。另外，现在的面试基本默认候选人有做过LC的经历，如果我没有做过一些基本的，那也就拉了行业的后腿了，逃。
综上，好东西，有价值，为啥不做呢？
总结：
（1）深度优先搜索和递归的思想。简单级别的树的题目基本都是关于DFS，核心在于将题目需要的信息在DFS的时候能够计算出来。
（2）深度优先遍历的代码模板，代码如下：
#获取树中的所有值
def dfs(root, vals):
if root:
vals.append(root.val)
dfs(root.left, vals)
dfs(root.right, vals)
vals = []
dfs(root, vals)
1.相同的树
2.对称二叉树
3.二叉搜索树的最近公共祖先
二叉搜索树的定义是：根节点的左儿子的值比根节点小，右儿子的值比根节点大。也就是说二叉搜索树是一个有序结构。对于有序结构的算法，想办法利用这种结构上的有序性显得非常重要。类似的包括：在找规律题目中，如何找到规律？
给定根节点root和两个任意给定的节点p和q，思路如下（默认情况下，比较都是基于节点的值）：
（1）如果q和q分别在root的左右子树，那么root就是最近公共祖先了。（这里写成代码，也就是一个退出条件。）
（2）如果p和q都小于root，也就是说p和q都在root的左子树，那么最近公共祖先一定在root的左子树。
（3）如果p和q都大于root，也就是说p和q都在root的右子树，那么最近公共祖先一定在root的右子树。
延伸思考：如果这个树是没有结构的呢？这是一道medium题目，二叉树的最近公共祖先。
4.二叉树的所有路径
题目描述：给定一个二叉树，返回所有从根节点到叶子节点的路径。其中，叶子节点是指没有子节点的节点。示例如下:
输入:
1
/ \
2 3
\
5
输出: ["1->2->5", "1->3"]
解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3
直接的想法是：从root节点开始，到叶子节点结束，做深度遍历。遍历访问可以通过记录得到一条访问路径，这里有趣的是记录path的方式。如下：
path = []
def dfs(path, root):
#到达叶子节点，可以直接return掉，该分支上的递归结束
if not root.left and not root.right:
path += [root.val,]
return
if root.left:
dfs(path+[root.val,], root.left)
if root.right:
dfs(path+[root.val,], root.right)
5.左叶子之和
题目描述：计算给定二叉树的所有左叶子之和。这里的问题是：如何判断一个节点是左叶子节点？，代码如下：
if root.left and not root.left.left and not root.left.right:
return True
6.二叉树的堂兄弟节点
题目描述：给定一棵二叉树和两个节点，判断这两个节点是否是堂兄弟节点。党兄弟节点的定义：如果二叉树的两个节点深度相同，但父节点不同，则它们是一对堂兄弟节点。这是一道经典的深度优先遍历的题目，代码如下：
def isCousins(root, x, y):
parent = {}
depth = {}
def dfs(root, par_node):
if root:
depth[root.val] = depth[par_node.val] + 1 if par_node else 0
parent[root.val] = par_node
dfs(root.left, root)
dfs(root.right, root)
dfs(root)
return depth[x] == depth[y] and parent[x] != parent[y]
值得注意的是：在DFS的同时，记录当前节点的深度和父节点。除了深度和父节点之外，结合题目自身的要求，很多信息都可以在DFS的时候进行记录。类似题目，从根到叶的二进制数之和。
不过，在结合Python的一些特性之后，比如Python3.3之后的yield from，可以写出更Pythonic的代码，看叶子相似的树这道题，一种牛逼的解法如下：
def leafSimilar(self, root1, root2):
def dfs(node):
if node:
if not node.left and not node.right:
yield node.val
yield from dfs(node.left)
yield from dfs(node.right)
return list(dfs(root1)) == list(dfs(root2))
7.腐烂的橘子
题目描述：在给定的网格中，每个单元格可以有以下三个值之一：
值 0 代表空单元格； 值 1 代表新鲜橘子； 值 2 代表腐烂的橘子。 每分钟，任何与腐烂的橘子（在 4 个正方向上）相邻的新鲜橘子都会腐烂。
返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1。
举例如下：
输入：[[2,1,1],[1,1,0],[0,1,1]]
输出：4
基本思路：前述题目都是关于DFS，这道题目是关于BFS，与BFS比较相关的数据结构是队列，在Python中，通常用deque。一种解法如下：
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
import collections
#获取二维数组的行和列的数目
x, y, time = len(grid), len(grid[0]), 0
#四个正方向上的偏移
locs = [[-1,0],[0,-1],[0,1],[1,0]]
deque = collections.deque()
#记录腐烂橘子的位置，同时带有一个time位置记录
for i in range(x):
for j in range(y):
if grid[i][j] == 2:
deque.append((i, j, 0))
#从队列中取元素，结合当前情况，更新状态，新元素入队
while deque:
i, j, time = deque.popleft()
for loc in locs:
loc_i, loc_j = i+loc[0], j+loc[1]
if 0 <= loc_i < x and 0 <= loc_j < y and grid[loc_i][loc_j] == 1:
grid[loc_i][loc_j] = 2
deque.append((loc_i, loc_j, time+1))
#最后做状态的判断
if any(1 in row for row in grid):
return -1
return time
总结一下整体的流程：
- 确定系统的边界：row和col的取值范围
- 定义状态的表达方式：4个正方向的表示，用坐标求和表示位置改变
- 确定队列的初始状态：找到烂橘子所在位置
- 队列更新：队列中的元素状态更新
- 最终的队列状态判断
总之，这是一道标准模板题。
8.员工的重要性
题目描述：给定一个保存员工信息的数据结构，它包含了员工唯一的id，重要度和直系下属的id。
比如，员工1是员工2的领导，员工2是员工3的领导。他们相应的重要度为15, 10, 5。那么员工1的数据结构是[1, 15, [2]]，员工2的数据结构是[2, 10, [3]]，员工3的数据结构是[3, 5, []]。注意虽然员工3也是员工1的一个下属，但是由于并不是直系下属，因此没有体现在员工1的数据结构中。
现在输入一个公司的所有员工信息，以及单个员工id，返回这个员工和他所有下属的重要度之和。这是一个示例：
输入: [[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], 1
输出: 11
解释:
员工1自身的重要度是5，他有两个直系下属2和3，而且2和3的重要度均为3。因此员工1的总重要度是 5 + 3 + 3 = 11。
该题其实是一道深搜题（DFS），代码如下：
def getImportance(self, employees, query_id):
emap = {e.id: e for e in employees}
def dfs(eid):
employee = emap[eid]
return (employee.importance +
sum(dfs(eid) for eid in employee.subordinates))
return dfs(query_id)
9.另一个树的子树
题目描述：给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s也可以看做它自身的一棵子树。
给定的树s，如下：
3
/ \
4 5
/ \
1 2
给定的树t，如下：
4
/ \
1 2
返回True。
给定的树s，如下：
3
/ \
4 5
/ \
1 2
/
0
给定的树t，如下：
4
/ \
1 2
返回False。
基本思路和判断两棵树是否相同类似，不过这里判断的是一棵树是否是另一棵树的子树。一种思路如下：
class Solution:
def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:
if not t:
return True
if not s:
return False
#问题的核心逻辑
return self.isSame(s,t) or self.isSubtree(s.left,t) or self.isSubtree(s.right,t)
#该函数也是一道经典题目
def isSame(self,p,q):
#两棵树的根节点都为空
if not p and not q:
return True
#如果不满足上述条件，存在一个为空，另一个不为空
if not p or not q:
return False
#判断树是否相同的条件，树的值相同
return p.val==q.val and self.isSame(p.left,q.left) and self.isSame(p.right,q.right)