代码随想录算法训练营第十六天| 530.二叉搜索树的最小绝对差、501.二叉搜索树中的众数、236. 二叉树的最近公共祖先

写代码的第十六天，自从到了二叉树错误版代码就少了，因为我自己根本没思路，都是看完思路在做，那基本上就是小语法问题，很少有其他问题了，证实了我好菜。。。。。。
还是得写思路啊啊啊啊，写思路好重要！！！

530.二叉搜索树的最小绝对差

思路

看见二叉搜索树，首先可以想到中序遍历，就变成了一个有序的数组，在数组中求相邻两个元素的最小绝对差。

class Solution:def getMinimumDifference(self, root: Optional[TreeNode]) -> int:mindif = float('inf')res = []self.traversal(root,res)for i in range(1,len(res)):diff = res[i] - res[i-1]mindif = min(mindif, diff)return mindifdef traversal(self,root,res):if root == None:return left = self.traversal(root.left,res)res.append(root.val)right = self.traversal(root.right,res)return res

思路（双指针）

要计算任意两个结点的最小值，还是按照左中右这样的顺序，因为这样计算的话每次都是从小到大的顺序，计算差值肯定相邻的一定比不相邻的小，在最开始我一直觉得万一最后一个数和第一个数的差值比其他的都小呢，其实这种情况根本不可能存在，就像上面的数组，最后一个数减去第一个数的差值不可能比他相邻的数减去第一个数的差值小。所以在这里设置两个结点变量，一个指向当前结点，一个指向当前结点的前一个结点，这两个结点都进行中序遍历，对这两个结点做减法，记录最小值，然后递归的进行中序遍历不断的判断，这个时候记录最小值的变量就应该设置为全局变量了，因为要存储最后的最小值，而不是每次递归都给他初始化成同一个值，它需要被记录。
正确代码：

class Solution:def __init__(self):self.mindif = float('inf')self.pre = Nonedef getMinimumDifference(self, root: Optional[TreeNode]) -> int:self.traversal(root)return self.mindifdef traversal(self,cur):if cur == None:returnself.traversal(cur.left)if self.pre != None:self.mindif = min(cur.val - self.pre.val,self.mindif)self.pre = curself.traversal(cur.right)

总结一下全局变量这一块，之前一直不知道全局变量用在哪，但是连着做了三四个题，我理解的全局变量就是在所有函数中进行操作这个变量他的值都会被存下来，会改变。如果放在函数体内的局部变量尤其是在递归的时候每次都会重复调用，如果像之前一样总是设置为0或者1这种，那么每次递归都从0或者1开始，肯定会报错。

501.二叉搜索树中的众数

思路

使用中序遍历（但其实好像哪种遍历都行，因为最后生成的是字典，不需要非得有序），在遍历过程中直接构建字典，然后遍历字典输出最大的那个value。
注释：如果你想将字典中所有键的初始值都设置为0，但不知道具体的键有哪些，你可以使用默认字典（defaultdict）来实现。defaultdict 是 collections 模块中的一个类，它是字典的一个子类，可以提供默认值来初始化字典中的键。

from collections import defaultdict
my_dict = defaultdict(lambda: 0)

错误第一版：第一处错误是在使用 defaultdict 初始化 mapdict 时，需要指定默认值的类型。你可以将 int 作为默认值类型，表示键的初始值为0。第二处错误是在遍历 mapdict 的键值对时，需要使用 items() 方法来获取键值对的迭代器，然后才能进行迭代。第三处错误是在 findMode() 方法中的 if root == None 分支中，你返回的是 None，而函数的返回类型应该是 List[int]。你可以返回一个空列表 [] 来表示没有找到任何模式。

from collections import defaultdict
class Solution:def findMode(self, root: Optional[TreeNode]) -> List[int]:result = []mapdict = defaultdict()if root == None:return self.searchBFS(root,mapdict)maxval = max(mapdict.values())for k,v in mapdict:if v == maxval:result.append(k)return resultdef searchBFS(self,root,mapdict):if root == None:return self.searchBFS(root.left,mapdict)mapdict[root.val] += 1self.searchBFS(root.right,mapdict)

正确代码：

from collections import defaultdict
class Solution:def findMode(self, root: Optional[TreeNode]) -> List[int]:result = []mapdict = defaultdict(int)if root == None:return []self.searchBFS(root,mapdict)maxval = max(mapdict.values())for k,v in mapdict.items():if v == maxval:result.append(k)return resultdef searchBFS(self,root,mapdict):if root == None:return self.searchBFS(root.left,mapdict)mapdict[root.val] += 1self.searchBFS(root.right,mapdict)

需要注意的一个地方是，众数可以有很多个，所以设置了result来存放。

思路（指针）

拿过来自己没思路，这个情况很烦啊，我一直想不通遍历的话不还是变成数组这样才能比较吗，指针就算是设置为一个cur一个pre和上面题一样也做不出来啊，怎么就判断这个是众数呢，就算判断了你怎么计数呢？这些问题我无法解决，我好痛苦。看了一下卡哥的思路，也是设置cur和pre两个指针，采用中序遍历，pre一直在cur前面，他俩永远是相邻的，只要判断这两个指针相等，那么这个数就出现了不止一次就可以说是众数，将其append进结果集中，但是如果当前遍历的众数出现了两次，但是之后有众数出现了三次，这种情况怎么解决呢，把当前结果集清空，然后将现在的结果append进结果姐，第一个问题解决了。那现在怎么计数呢，当出现pre和cur的值是相等的时候，count计数器加一，一旦pre和cur不相等count直接变成1，重新从1开始计数。记得要更新pre。
现在来解决递归的三个基本条件：
解决问题1:参数和返回值？我们设置了存储最后众数的结果集，pre指针，但是这些都已经设置在全局变量中了，所以参数只需要cur。因为要遍历完整颗树并不需要在过程中停止，所以不需要返回值，同时需要修改的值已经在全局变量中设置好了，也不需要返回。
解决问题2:终止条件？当cur为空的时候，就证明树遍历结束了，但是我们不需要返回值，所以return就行。
解决问题3:单层递归逻辑？pre在cur前面，不停的比较cur和pre的值，如果相等，将这个值append进result中，count也就是出现次数加一；当pre不等与cur的值的时候将count的值赋值给maxcount，然后将count=1，用这一步把现在出现的众数的出现最大次数计数，更新maxcount；然后继续遍历继续找，如果有出现count大于maxcount的情况的时候就把result全部清空，然后将新的这个结点的值append进result中，更新maxcount，直到终止条件。
错误第一版：

from collections import defaultdict
class Solution:def __init__(self):self.pre = Noneself.result = []self.count = 1self.maxcount = float('-inf')def traversal(self,cur):if cur == None:return self.traversal(cur.left)if self.pre != None and self.pre.val == cur.val:self.count += 1self.result.append(cur.val)if self.pre != None and self.pre.val != cur.val:self.maxcount = self.countself.count = 1if self.count > self.maxcount:self.result.clear()self.result.append(cur.val)self.traversal(cur.right)def findMode(self, root: Optional[TreeNode]) -> List[int]:self.traversal(root)return self.result

再次整理思路：只看单次递归这里，先计数在和maxcount比较，然后再决定要不要进result。如果pre和cur的值相等那么count+1，如果不相等，那么count=1；然后再将count和maxcount进行比较，如果count等于maxcount，那么将当前的结点值append进result，如果count小于maxcount不做任何操作，如果count大于maxcount那么更新maxcount = count并且将result全部清空，然后将现在的值append进result。
正确代码：

from collections import defaultdict
class Solution:def __init__(self):self.pre = Noneself.result = []self.count = 1self.maxcount = 0def traversal(self,cur):if cur == None:return self.traversal(cur.left)if self.pre != None and self.pre.val == cur.val:self.count += 1if self.pre != None and self.pre.val != cur.val:self.count = 1self.pre = curif self.count == self.maxcount:self.result.append(cur.val)if self.count > self.maxcount:self.maxcount = self.countself.result.clear()  # 先清空 result 列表self.result.append(cur.val)self.traversal(cur.right)def findMode(self, root: Optional[TreeNode]) -> List[int]:self.traversal(root)return self.result

236. 二叉树的最近公共祖先

思路

因为是想找最近公共祖先，所以后序遍历最好。(没审题我真的会谢，我一直挣扎与万一p或者q不在这个树中咋办啊，结果题里面写了p 和 q 均存在于给定的二叉树中，我真该啊。。。)
解决问题1:参数和返回值是什么？在本题中参数是root以及p和q两个结点，返回值就是最近公共祖先。
解决问题2:终止条件是什么？如果在遍历的过程中在左子树出现q右子树出现p或者左子树出现p右子树出现q那么就说明公共祖先存在，返回此时左右子树的上一个，也就是左右中遍历的中结点；如果遍历了整颗树（也就是root==None的情况）只存在一个或者两个都不存在，那么返回None，没有公共祖先。
解决问题3:单次递归的逻辑是什么？根据下面的解释，本题中单次递归是左右都需要遍历的，并且需要返回值的。按照后序遍历左右中的情况，先递归左子树，然后递归右子树，最后处理中结点，其实中结点是我们的主要处理位置。中结点需要判断的是其左右子树是否存在q和p，如果两个都存在，那么向上一层返回
补充：这个部分是我经常会产生疑问的，卡哥说的非常清晰，记一下嘿嘿嘿。



错误第一版：就因为挣扎于万一有p或者q不在树中怎么办，其实题中说的很明确了，q和p一定存在。错误是解答错误，思路还是有点问题。

class Solution:def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':if root == None:return  left = self.lowestCommonAncestor(root.left,p,q)right = self.lowestCommonAncestor(root.right,p,q)if left != None and right == None:return rightelif left == None and right != None:return leftelse:return root

重新整理思路：在终止条件这里，一种情况是遍历完整颗树也就是root==None的时候那么返回root其实也就是None（需要注意一下我之前理解的终止条件总以为是最后的输出值，其实不是，他就只是最后一次递归的值，我们还要回溯回去呢），第二种情况就是当root结点就是q或者p的时候根据题意p和q是一定存在的，那么当前已经遍历到了q或者p那就证明剩下的那个一定在他下面的树中，所以q或者p就是他们自己的公共祖先。再说一下单次递归这里，如果遍历了left和right但是这两个里面都是有返回值的，也就是存在p或q那么就直接返回root也就是他们的上一个结点，如果只有left或者right有值，那就证明p和q存在于一侧，所以只返回那一侧就可以了，如果遍历完成了没有任何一个地方存在，那就返回None。
正确代码：

class Solution:def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':if root == None:return rootif root == q or root == p:return rootleft = self.lowestCommonAncestor(root.left,p,q)right = self.lowestCommonAncestor(root.right,p,q)if left != None and right == None:return leftelif left == None and right != None:return rightelif left != None and right != None:return rootelse:return None