参考文章：https://www.hello-algo.com/ 代码地址：https://github.com/Liucc-123/datastructure

1、二叉树

1.1、二叉树的基本概念

• 定义：二叉树是一种非线性数据结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。

• 节点结构：每个节点包含：

  • 一个值（val）
  • 一个指向左子节点的引用（left）
  • 一个指向右子节点的引用（right）

  /* 二叉树节点类 */
  class TreeNode {
      int val;         // 节点值
      TreeNode left;   // 左子节点引用
      TreeNode right;  // 右子节点引用
      TreeNode(int x) { val = x; }
  }
  

在树结构中，每个节点都有两个指针，分别指向左子节点和右子节点，该节点被称为这两个字节点的父结点。其左子节点及其以下所有节点所形成的树称为该节点的左子树。同理，可得右子树。

**在二叉树中，除了叶子节点，其他所有节点都包括子节点和非空子树。**如下图，如果将节点 2 视为父结点，那么节点 4 是其左子节点，节点 5 是其右子节点，节点 4 及其底下所有节点形成的树是节点 2 的左子树，节点 5 及其底下所有节点形成的树称为节点 2 的右子树。

1.2、二叉树的常见术语：

• 根节点：位于顶层，没有父节点。
• 叶节点：没有子节点的节点，两个指针均指向 null。
• 边：连接两个节点的线段。
• 节点所在的层：从根节点开始，逐层向下递增，根节点所在的层是 1。
• 节点的度：节点的子节点的数量。在二叉树中，节点的度的取值范围是0、1 或 2。
• 节点的深度：从根节点到该节点所经过边的数量。
• **节点的高度：**从该节点到最远叶节点所经过边的数量。
• 二叉树的高度：从根节点到最远叶节点的边的数量。

<aside> ⚠️

请注意，我们通常将“高度”和“深度”定义为“经过的边的数量”，但有些题目或教材可能会将其定义为“经过的节点的数量”。在这种情况下，高度和深度都需要加 1 。

</aside>

1.3、 二叉树的基本操作