【JavaScript】数据结构之树
什么是树形结构？
- 一种分层数据的抽象模型，用来分层级关系的。
- 虚拟dom它所组织的那个数据原理就是树形结构
深度优先搜索（遍历）- 递归
- 从根出发，尽可能深的搜索树的节点
- 技巧
- 访问根节点
- 对根节点的children挨个进行深度优化搜索
广度优先搜索（遍历）
- 从根出发，优先访问离根节点最近的节点
- 最近公共祖先节点可以为节点本身。
- 技巧
- 新建一个队列，把根节点入队
- 把队头出队
- 把队头的children挨个入队
- 重复上面二三步骤，直到队列为空为止
树 - 多叉树
- dom结构是典型的多叉树
树 - 二叉树
- 前序遍历 & 先序遍历
- 规则：根 左 右
- 先从根出发 > 拿左子树的左 > 拿左子树的右，等左边都结束 > 再拿右子树的左 > 拿右子树的右
- 可以通过递归算法实现，也可以通过迭代算法（栈）实现。
- 中序遍历
- 规则：左 根 右
- 后序遍历
- 规则：左 右 根
leetcode 习题
二叉树习题