树

树是一种非线性数据结构，它由节点（Node）和边（Edge）组成。树的每个节点可以有零个或多个子节点，但每个节点只有一个父节点，除了根节点。

几个关键概念

1. 树的层次计算规则：根结点所在的那一层记为第一层，其子结点所在的就是第二层，以此类推。
2. 结点和树的“高度”计算规则： 叶子结点高度记为 1，每向上一层高度就加 1，逐层向上累加至目标结点时，所得到的的值就是目标结点的高度。树中结点的最大高度，称为“树的高度”。
3. “度”的概念：一个结点开叉出去多少个子树，被记为结点的“度”。
4. 叶子结点：叶子结点就是度为 0 的结点。在上图中，最后一层的结点的度全部为 0，所以这一层的结点都是叶子结点。

二叉树

二叉树是一种特殊的树，每个节点最多有两个子节点，分别称为左子节点和右子节点。

注意，二叉树不能被简单定义为每个结点的度都是 2 的树。普通的树并不会区分左子树和右子树，但在二叉树中，左右子树的位置是严格约定、不能交换的。

二叉树的编码实现

class TreeNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

二叉树的遍历

二叉树的遍历方式有三种：前序遍历、中序遍历和后序遍历。

• 前序遍历：先访问根节点，然后访问左子树，最后访问右子树。
• 中序遍历：先访问左子树，然后访问根节点，最后访问右子树。
• 后序遍历：先访问左子树，然后访问右子树，最后访问根节点。