《刷题健身两不误》龙傲天转世

20、8.19 二叉树结束

　　快速排序详解及应用：
　　终于理解了快速排序不仅是二叉树的前序，也可以说快速排序的过程是一个构造二叉搜索树的过程。但谈到二叉搜索树的构造，那就不得不说二叉搜索树不平衡的极端情况，极端情况下二叉搜索树会退化成一个链表，导致操作效率大幅降低。这样的话，时间复杂度会大幅上升。
　　快速排序是「不稳定排序」，与之相对的，前文学到的归并排序是「稳定排序」。
　　215. 数组中的第K个最大元素
　　哈哈哈哈，sort方可解所有。最后复习了一下快排，这题目的神奇之处就是快排后，因为是求第k个最大元素，所以需要用一个二分，然后再写一次递归，从而得出最终答案。
　　912. 排序数组
　　这题目用的是归并排序，然后我试了试快排，超时了，但是巩固了一下。

　　题目不让我干什么，我偏要干什么：
　　341. 扁平化嵌套列表迭代器
　　我先开始读不懂意思，后面知道意思了，就是用栈将其全部变成int型，但是我又看不懂注释了
　　还有一种思路，就是这题其实就是二叉树的遍历，但是我不太会这个操作
　　寄希望于修勾，呜呜呜呜呜呜，又是想修勾的一天

　　GIT原理之最近公共祖先：
　　235. 二叉搜索树的最近公共祖先
　　这题既可以用前序遍历也可以用后序遍历，后序遍历实际运行的效率会低一点，相当于先去左右子树找，然后才检查 root，这种写法必然会遍历二叉树的每一个节点。
　　对于之前的解法，你在前序位置就检查 root，如果输入的二叉树根节点的值恰好就是目标值 val，那么函数直接结束了，其他的节点根本不用搜索。
　　但如果你在后序位置判断，那么就算根节点就是目标节点，你也要去左右子树遍历完所有节点才能判断出来。
　　236. 二叉树的最近公共祖先
　　超级简单呀呀
　　ps:这两题都是确定公共祖先一定存在，如果它给予的不是几个数值而是数组，那需要将列表转化成哈希集合，便于判断元素是否存在。

　　如何计算完全二叉树的节点数：
　　222. 完全二叉树的节点个数
　　嘻嘻嘻嘻，很简单的呀