【九月打卡】第18天 前端面试技能拼图1

课程名称：2周刷完100道前端优质面试真题
课程章节：第3章 前端面试技能拼图1： 数据结构和算法（下），大厂面试必考
主讲老师：双越

课程内容：

今天学习的内容包括：
3-1 求二叉搜索树的第K小值-二叉树和三种遍历——二叉树的前中后序遍历。
3-2 求二叉搜索树的第K小值-解题——利用二叉树的特征快速查找到对应的第K小值。

课程收获：

求二叉搜索树的第K小值

二叉树：Binary Tree

• 是一棵树
• 每个节点，最多有两个子节点
• 树节点的数据结构 { value, left, right? }

二叉树的遍历

• 前序遍历：root -> left -> right
• 中序遍历：left -> root -> right
• 后序遍历：left -> right -> root

二叉搜索树BST：binary search tree

• left （包括其后代) value <= root.value
• right (包括其后代) value >= root.value
• 可使用二分法进行快速查找

解题思路

• BST中序遍历，即从小到大的排序
• 找到排序后的第k值即可

划重点

• 二叉树，和三种（前序、中序、后序）遍历
• 二叉搜索树的特点：left <= root；right >= root
• 二叉搜索树的价值：可使用二分法进行快速查找

今天的 学习了 求二叉搜索树的第K小值，二分法主要特性为 左节点小于根节点，右节点大于根节点，雷勇二叉树的特征可以快速找到对应的第K小值，如果只是查找，我觉得可以将步数传入，查到时直接返回，这样性能更好，目前课程中是先全量放入数组，在取值。

下一步就是 学习 为什么二叉树很重要，而不是三叉树四岔树 了。今天学习就先到这里吧。

坚持打卡，坚持学习，未来可期，加油&#128512;~

​​

​