【008-week2】算法训练营第二周学习总结

[UCSBGauchos]

学习心得：
这周主要挑了几套hash表和二叉树的题目。对于hash表，个人的感觉是一定要理清楚hash表的定义，因为一个好的hash表对解题是由事半功倍的效果的。
比如：Leetcode#242 有效的字母异位词
这道题目的难点在于单词中可能存在多个相同的字符，常用的简单KV需要使用整数来表示value
而对于二叉树，怎样抽象递归地模板，怎样高效地利用递归来处理问题也是一个难点。
比如：Leetcode#236 二叉树的最近公共祖先
这道题本来的解法是这样的，相当于要双重递归了，先DFS每个根节点，然后对每个根节点的左右子树，分别再使用DFS来判断目标节点是否包含在书中。就算使用了一些剪枝的技巧，也超时。然后就想了，是否可以一次递归就搞定，答案是肯定的。优化的思路在于，节点一定都存在，所以只要right == null，就可以断定都在left中，并且祖先就是left。反之亦然，后期还是需要多多练习。

[Jerrydreamaker]

最近祖先确实是比较绕，如果左右都不空，可以结束整个递归，当前节点即最近父节点。