# 二叉树 - 概述

二叉树的定义是：树中每一个节点最多只有两个 孩子，如比说 下图中的 1 跟 3 它们各自都有 两个孩子

当然也可以只有一个孩子，也可以没有孩子

没有孩子的节点 称之为 叶子节点 而树的 起始节点 1 称之为 根节点 也叫 root 节点

二叉树的存储方式 ，可以用 树节点来 表示二叉树，另外一种就是用数组来表示二叉树

# 遍历

# 遍历也分为两种

1. 广度优先遍历 (Breadth-first order)：尽可能先访问距离跟最近的节点，也称为 层序遍历
   • 层序遍历 - 在之前的 leetcode 题中 有写过 就是 先拿到根节点判断有无左右孩子 从左向右遍历
2. 深度优先遍历 (Depth-first order)：对于二叉树，可以进一步分成三种
   1. pre-order 前序遍历：对于每一颗子树，先访问该节点，然后是左子树，最后是右子树
   2. in-order 中序遍历：对于每一颗子树，先访问左子树，然后是该节点，最后是右子树
   3. post-order：后续遍历：对于每一颗子树，先访问左子树，然后是右子树，最后是该节点

注意：

我们之前学过的 使用 队列 来实现 二叉树的 层序遍历它针对的是使用 TreeNode 这种方式表示的二叉树

如果我们使用数组来实现二叉树 那么实际上直接遍历数组就可以，它的顺序自然就是 层序遍历的 顺序

如下图所示：

下面是数组实现的二叉树那么它的层序遍历就是 从 0 到 数组尾 依次遍历就是 二叉树的每一层的顺序

0 索引 是 第一层

1, 2 索引 是 第二层

3， 4， 5， 6 索引 是 第三层

所以是数组实现的二叉树的话那直接遍历这个数组 它自然就是层序遍历