数据结构——树

由 n ≥ 0 个节点与节点之间的关系组成的有限集合。当 n=0时称为空树，当 n>0 时称为非空树

一、树的概念

之所以把这种数据结构称为「树」是因为这种数据结构看起来就像是一棵倒挂的树，也就是说数据结构中的「树」是根朝上，而叶朝下的。如下图所示

1. 特点

• 有且仅有一个节点没有前驱节点，该节点被称为树的 「根节点（Root）」 。
• 除了根节点以之，每个节点有且仅有一个直接前驱节点。
• 包括根节点在内，每个节点可以有多个后继节点。
• 当 n>1 时，除了根节点之外的其他节点，可分为 m(m>0) 个互不相交的有限集合 T1,T2,Tm，其中每一个集合本身又是一棵树，并且被称为根的 「子树（SubTree）」

如下图所示，红色节点 AAA 是根节点，除了根节点之外，还有 3 棵互不相交的子树 T1、T2、T3

2. 树的相关术语

2.1. 节点分类

「树的节点」 由一个数据元素和若干个指向其子树的树的分支组成。而节点所含有的子树个数称为 「节点的度」。度为 000 的节点称为 「叶子节点」 或者 「终端节点」，度不为 000 的节点称为 「分支节点」 或者 「非终端节点」。树中各节点的最大度数称为 「树的度」

• 树的节点：由一个数据元素和若干个指向其子树的树的分支组成。
• 节点的度：一个节点所含有的子树个数。
• 叶子节点（终端节点）：度为 000 的节点。例如图中叶子节点为 C、H、I、G、F、K。
• 分支节点（非终端节点）：度不为 000 的节点。例如图中分支节点为 A、B、D、E、G。
• 树的度：树中节点的最大度数。例如图中树的度为 333

2.2. 节点间关系

一个节点的子树的根节点称为该节点的 「孩子节点」，相应的，该节点称为孩子的 「父亲节点」。同一个父亲节点的孩子节点之间互称为 「兄弟节点」

• 孩子节点（子节点）：一个节点含有的子树的根节点称为该节点的子节点。例如图中 B 是 A 的孩子节点。
• 父亲节点（父节点）：如果一个节点含有子节点，则这个节点称为其子节点的父节点。例如图中 B 是 E 的父亲节点。
• 兄弟节点：具有相同父节点的节点互称为兄弟节点。例如图中 F、G 互为兄弟节点

3. 树的分类

根据节点的子树是否可以互换位置，我们可以将树分为两种类型：「有序树」 和 「无序树」。

如果将树中节点的各个子树看做是从左到右是依次有序的（即不能互换），则称该树为 「有序树」。反之，如果节点的各个子树可以互换位置，则成该树为 「无序树」。

• 有序树：节点的各个⼦树从左⾄右有序， 不能互换位置。
• 无序树：节点的各个⼦树可互换位置。

二、二叉树

树中各个节点的度不大于 2 个的有序树，称为二叉树。通常树中的分支节点被称为 「左子树」 或 「右子树」。二叉树的分支具有左右次序，不能随意互换位置

1. 概念

二叉树满足以下两个要求之一：

• 空树：二叉树是一棵空树。
• 非空树：二叉树是由一个根节点和两棵互不相交的子树 T1T2，分别称为根节点的左子树、右子树组成的非空树；并且 T1T2 本身都是二叉树。

⼆叉树是种特殊的树，它最多有两个⼦树，分别为左⼦树和右⼦树，并且两个子树是有序的，不可以互换。也就是说，在⼆叉树中不存在度⼤于 2 的节点

二叉树在逻辑上可以分为 5 种基本形态，如下图所示

2. 特殊的二叉树

2.1. 满二叉树

如果所有分支节点都存在左子树和右子树，并且所有叶子节点都在同一层上，则称该二叉树为满二叉树

• 叶子节点只出现在最下面一层。
• 非叶子节点的度一定为 222。
• 在同等深度的二叉树中，满二叉树的节点个数最多，叶子节点个数最多

2.2. 完全二叉树

如果叶子节点只能出现在最下面两层，并且最下层的叶子节点都依次排列在该层最左边的位置上，具有这种特点的二叉树称为完全二叉树

• 叶子节点只能出现在最下面两层。
• 最下层的叶子节点一定集中在该层最左边的位置上。
• 倒数第二层如果有叶子节点，则该层的叶子节点一定集中在右边的位置上。
• 如果节点的度为 1，则该节点只偶遇左孩子节点，即不存在只有右子树的情况。
• 同等节点数的二叉树中，完全二叉树的深度最小

2.3. 二叉搜索树

也叫做二叉查找树、有序二叉树或者排序二叉树。是指一棵空树或者具有下列性质的二叉树：

• 如果任意节点的左子树不为空，则左子树上所有节点的值均小于它的根节点的值。
• 如果任意节点的右子树不为空，则右子树上所有节点的值均大于它的根节点的值。
• 任意节点的左子树、右子树均为二叉搜索树。

2.4. 平衡二叉搜索树

一种结构平衡的二叉搜索树。即叶节点高度差的绝对值不超过 111，并且左右两个子树都是一棵平衡二叉搜索树。平衡二叉树可以在 O(logn)O(logn)O(logn) 内完成插入、查找和删除操作。最早被发明的平衡二叉搜索树为 「AVL 树（Adelson-Velsky and Landis Tree））」

• 空二叉树是一棵 AVL 树。
• 如果 T 是一棵 AVL 树，那么其左右子树也是 AVL 树，并且 h(ls) − h(rs) ≤ 1 。 其中h(ls) 是左子树的高度，h(rs) 是右子树的高度。
• AVL 树的高度为 O(logn)

三、二叉树的遍历

指的是从根节点出发，按照某种次序依次访问二叉树中所有节点，使得每个节点被访问一次且仅被访问一次

1. 概念

在二叉树的一些实际问题中，经常需要按照一定顺序对二叉树中每个节点逐个进行访问一次，用以查找具有某一特点的节点或者全部节点，然后对这些满足要求的节点进行处理。这里所说的「访问」就是指对该节点进行某种操作，例如：依次输出节点的数据信息、统计满足某条件的节点总数等等。

回顾二叉树的定义可以知道，二叉树是由根节点和左子树、右子树构成的。因此，如果能依次遍历这 3 个部分，就可以遍历整个二叉树

如果利用深度优先搜索的方式，并且根据访问顺序次序的不同，我们可以分为 6 种遍历方式，而如果限制先左子树后右子树的遍历顺序，则总共有 3 种遍历方式：分别为 「二叉树的前序遍历」、「二叉树的中序遍历」 和 「二叉树的后续遍历」。

而如果使用广度优先搜索的方式，则可以按照层序方式（按照层次从上至下，每一层从左至右）对二叉树进行遍历，这种方式叫做 「二叉树的层序遍历」

2. 二叉树的前序遍历

二叉树的前序遍历规则为：

• 如果二叉树为空，则返回。
• 如果二叉树不为空，则：

1. 1. 访问根节点。
   2. 以前序遍历的方式遍历根节点的左子树。
   3. 以前序遍历的方式遍历根节点的右子树

2.1. 思路

1. 判断二叉树是否为空，为空则直接返回。
2. 先访问根节点。
3. 然后递归遍历左子树。
4. 最后递归遍历右子树

2.2. 代码

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

class Solution {
  preorderTraversal(root) {
    const res = []; // 存储前序遍历结果的数组

    function preorder(node) {
      if (node) {
        res.push(node.val); // 将当前节点的值添加到结果数组
        preorder(node.left); // 递归遍历左子树
        preorder(node.right); // 递归遍历右子树
      }
    }

    preorder(root); // 调用前序遍历函数开始遍历
    return res; // 返回前序遍历结果数组
  }
}

// 创建二叉树
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);

const solution = new Solution();
const result = solution.preorderTraversal(root);
console.log(result); // 输出前序遍历结果 [1, 2, 4, 5, 3]

3. 二叉树的中序遍历

二叉树的中序遍历规则为：

• 如果二叉树为空，则返回。
• 如果二叉树不为空，则：

1. 1. 以中序遍历的方式遍历根节点的左子树。
   2. 访问根节点。
   3. 以中序遍历的方式遍历根节点的右子树

3.1. 思路

1. 判断二叉树是否为空，为空则直接返回。
2. 先递归遍历左子树。
3. 然后访问根节点。
4. 最后递归遍历右子树

3.2. 代码

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

class Solution {
  inorderTraversal(root) {
    const res = []; // 存储中序遍历结果的数组

    function inorder(node) {
      if (node) {
        inorder(node.left); // 递归遍历左子树
        res.push(node.val); // 将当前节点的值添加到结果数组
        inorder(node.right); // 递归遍历右子树
      }
    }

    inorder(root); // 调用中序遍历函数开始遍历
    return res; // 返回中序遍历结果数组
  }
}

// 创建二叉树
const root = new TreeNode(1);
root.right = new TreeNode(2);
root.right.left = new TreeNode(3);

const solution = new Solution();
const result = solution.inorderTraversal(root);
console.log(result); // 输出中序遍历结果 [1, 3, 2]

4. 二叉树的后序遍历

二叉树的后序遍历规则为：

• 如果二叉树为空，则返回。
• 如果二叉树不为空，则：

1. 1. 以后序遍历的方式遍历根节点的左子树。
   2. 以后序遍历的方式遍历根节点的右子树。
   3. 访问根节点

4.1. 思路

1. 判断二叉树是否为空，为空则直接返回。
2. 先递归遍历左子树。
3. 然后递归遍历右子树。
4. 最后访问根节点

4.2. 代码

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

class Solution {
  postorderTraversal(root) {
    const res = []; // 存储后序遍历结果的数组

    function postorder(node) {
      if (node) {
        postorder(node.left);   // 递归遍历左子树
        postorder(node.right);  // 递归遍历右子树
        res.push(node.val);     // 将当前节点的值添加到结果数组
      }
    }

    postorder(root); // 调用后序遍历函数开始遍历
    return res; // 返回后序遍历结果数组
  }
}

// 创建二叉树
const root = new TreeNode(1);
root.right = new TreeNode(2);
root.right.left = new TreeNode(3);

const solution = new Solution();
const result = solution.postorderTraversal(root);
console.log(result); // 输出后序遍历结果 [3, 2, 1]

5. 三者区别

前序遍历、中序遍历和后序遍历都是深度优先搜索（DFS）二叉树的方式，它们之间的区别在于访问节点的顺序和位置

5.1. 前序遍历 (Preorder Traversal)

先访问根节点。

然后递归遍历左子树。

最后递归遍历右子树。

根节点总是在最前面。

5.2. 中序遍历 (Inorder Traversal)

先递归遍历左子树。

然后访问根节点。

最后递归遍历右子树。

根节点位于左右子树之间。

5.3. 后序遍历 (Postorder Traversal)

先递归遍历左子树。

然后递归遍历右子树。

最后访问根节点。

根节点总是在最后面

6. 二叉树的层序遍历(广度优先)

二叉树的层序遍历规则为：

• 如果二叉树为空，则返回。
• 如果二叉树不为空，则：

1. 1. 先依次访问二叉树第 1 层的节点。
   2. 然后依次访问二叉树第 2 层的节点。
   3. ……
   4. 依次下去，最后依次访问二叉树最下面一层的节点

6.1. 思路

1. 判断二叉树是否为空，为空则直接返回。
2. 令根节点入队。
3. 当队列不为空时，求出当前队列长度 sis_isi。
4. 依次从队列中取出这 sis_isi 个元素，并对这 sis_isi 个元素依次进行访问。然后将其左右孩子节点入队，然后继续遍历下一层节点。
5. 当队列为空时，结束遍历

6.2. 代码

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

class Solution {
  levelOrder(root) {
    if (!root) {
      return []; // 如果根节点为空，返回空数组
    }

    const queue = [root]; // 创建一个队列，并将根节点入队
    const order = []; // 用于存储层序遍历结果的二维数组

    while (queue.length > 0) {
      const level = []; // 存储当前层的节点值
      const size = queue.length; // 当前层的节点个数

      for (let i = 0; i < size; i++) {
        const curr = queue.shift(); // 出队当前节点
        level.push(curr.val); // 将当前节点的值添加到当前层数组

        if (curr.left) {
          queue.push(curr.left); // 如果有左子节点，将左子节点入队
        }
        if (curr.right) {
          queue.push(curr.right); // 如果有右子节点，将右子节点入队
        }
      }

      order.push(level); // 将当前层的节点值数组添加到结果中
    }

    return order; // 返回层序遍历结果
  }
}

// 创建二叉树
const root = new TreeNode(3);
root.left = new TreeNode(9);
root.right = new TreeNode(20);
root.right.left = new TreeNode(15);
root.right.right = new TreeNode(7);

const solution = new Solution();
const result = solution.levelOrder(root);
console.log(result); // 输出层序遍历结果

四、二叉树的还原（创建）

指的是通过二叉树的遍历序列，还原出对应的二叉树

从二叉树的遍历过程可以看出，给定一棵非空二叉树，它的前序、中序、后续遍历所得到的遍历序列都是唯一的。那么反过来，如果已知节点的某种遍历序列，能否确定这棵二叉树呢？并且确定的二叉树是否是唯一的呢？🤔

先来看二叉树的前序遍历，前序遍历过程中首先访问的是根节点，所以通过前序遍历序列，我们可以确定序列的第 1个节点肯定是根节点。但是从第 2 个节点开始就不确定它是根节点的左子树还是根节点的右子树了。所以单凭前序遍历序列是无法恢复一棵二叉树的。

再来看二叉树的后序遍历，后序遍历也是只能确定序列的最后一个节点为根节点，而无法确定其他节点在二叉树中的位置。所以单凭后序遍历序列也是无法恢复一棵二叉树的。

最后我们来看二叉树的中序遍历，中序遍历是先遍历根节点的左子树，然后访问根节点，最后遍历根节点的右子树。这样，根节点在中序遍历序列中必然将中序序列分割成前后两个子序列，其中前一个子序列是根节点的左子树的中序遍历序列，后一个子序列是根节点的右子树的中序遍历序列。当然单凭中序遍历序列也是无法恢复一棵二叉树的

🤔

但是如果我们可以将「前序遍历序列」和「中序遍历序列」相结合，那么我们就可以通过上面中序遍历序列中的两个子序列，在前序遍历序列中找到对应的左子序列和右子序列。在前序遍历序列中，左子序列的第 1 个节点是左子树的根节点，右子序列的第 1 个节点是右子树的根节点。这样，就确定了二叉树的 3 个节点。同时，左子树和右子树的根节点在中序遍历序列中又可以将左子序列和右子序列分别划分成两个子序列。如此递归下去，当确定了前序遍历序列中的所有节点时，我们就得到了一棵二叉树

结论：

如果已知一棵二叉树的前序序列和中序序列，可以唯一地确定这棵二叉树

如果已知一棵二叉树的中序序列和后序序列，也可以唯一地确定这棵二叉树

已知二叉树的「中序遍历序列」和「层序遍历序列」，也可以唯一地确定一棵二叉树

1. 从前序与中序遍历序列构造二叉树

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

class Solution {
  // 主要方法，用于构建二叉树
  buildTree(preorder, inorder) {
    return this.createTree(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
  }

  // 递归方法，用于构建子树
  createTree(preorder, inorder, preStart, preEnd, inStart, inEnd) {
    if (preStart > preEnd || inStart > inEnd) {
      return null; // 基本情况：序列为空，返回空节点
    }

    const rootVal = preorder[preStart]; // 根据前序遍历序列的第一个值确定根节点的值
    const root = new TreeNode(rootVal); // 创建根节点

    let inIndex = inorder.indexOf(rootVal); // 在中序遍历中找到根节点的位置
    let leftSize = inIndex - inStart; // 计算左子树的大小

    // 递归构建左子树和右子树
    root.left = this.createTree(preorder, inorder, preStart + 1, preStart + leftSize, inStart, inIndex - 1);
    root.right = this.createTree(preorder, inorder, preStart + leftSize + 1, preEnd, inIndex + 1, inEnd);

    return root; // 返回根节点
  }
}

// 示例用法
const solution = new Solution();
const preorder = [3, 9, 20, 15, 7];
const inorder = [9, 3, 15, 20, 7];
const root = solution.buildTree(preorder, inorder);
console.log(root);

2. 从中序与后序遍历序列构造二叉树

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

class Solution {
  // 主要方法，用于构建二叉树
  buildTree(inorder, postorder) {
    return this.createTree(inorder, postorder, 0, inorder.length - 1, 0, postorder.length - 1);
  }

  // 递归方法，用于构建子树
  createTree(inorder, postorder, inStart, inEnd, postStart, postEnd) {
    if (inStart > inEnd || postStart > postEnd) {
      return null; // 基本情况：序列为空，返回空节点
    }

    const rootVal = postorder[postEnd]; // 根据后序遍历序列的最后一个值确定根节点的值
    const root = new TreeNode(rootVal); // 创建根节点

    let inIndex = inorder.indexOf(rootVal, inStart); // 在中序遍历中找到根节点的位置
    let leftSize = inIndex - inStart;

    // 递归构建左子树和右子树
    root.left = this.createTree(inorder, postorder, inStart, inIndex - 1, postStart, postStart + leftSize - 1);
    root.right = this.createTree(inorder, postorder, inIndex + 1, inEnd, postStart + leftSize, postEnd - 1);

    return root; // 返回根节点
  }
}

// 示例用法
const solution = new Solution();
const inorder = [9, 3, 15, 20, 7];
const postorder = [9, 15, 7, 20, 3];
const root = solution.buildTree(inorder, postorder);
console.log(root);

3. 从前序与后序遍历序列构造二叉树

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

class Solution {
  // 主要方法，用于构建二叉树
  constructFromPrePost(preorder, postorder) {
    return this.createTree(preorder, postorder, 0, preorder.length - 1, 0, postorder.length - 1);
  }

  // 递归方法，用于构建子树
  createTree(preorder, postorder, preStart, preEnd, postStart, postEnd) {
    if (preStart > preEnd || postStart > postEnd) {
      return null; // 基本情况：序列为空，返回空节点
    }

    const rootVal = preorder[preStart]; // 根据前序遍历序列的第一个值确定根节点的值
    const root = new TreeNode(rootVal); // 创建根节点

    if (preStart === preEnd) {
      return root; // 基本情况：序列长度为 1，返回根节点
    }

    const postIndex = postorder.indexOf(preorder[preStart + 1]); // 在后序遍历中找到根节点的位置
    const leftSize = postIndex - postStart + 1;

    // 递归构建左子树和右子树
    root.left = this.createTree(preorder, postorder, preStart + 1, preStart + leftSize, postStart, postIndex);
    root.right = this.createTree(preorder, postorder, preStart + leftSize + 1, preEnd, postIndex + 1, postEnd - 1);

    return root; // 返回根节点
  }
}

// 示例用法
const solution = new Solution();
const preorder = [3, 9, 20, 15, 7];
const postorder = [9, 15, 7, 20, 3];
const root = solution.constructFromPrePost(preorder, postorder);
console.log(root);

五、二叉搜索树

左子树的节点值 < 根节点值 < 右子树的节点值

1. 二叉树搜索树的查找

在二叉搜索树中查找值为 val 的节点

1.1. 思路

按照二叉搜索树的定义，在进行元素查找时，我们只需要根据情况判断需要往左还是往右走。这样，每次根据情况判断都会缩小查找范围，从而提高查找效率。二叉树的查找步骤如下：

1. 如果二叉搜索树为空，则查找失败，结束查找，并返回空指针节点 None。
2. 如果二叉搜索树不为空，则将要查找的值 val 与二叉搜索树根节点的值 root.val 进行比较：

1. 1. 如果 val == root.val，则查找成功，结束查找，返回被查找到的节点。
   2. 如果 val < root.val，则递归查找左子树。
   3. 如果 val > root.val，则递归查找右子树

1.2. 代码

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

class Solution {
  searchBST(root, val) {
    if (!root) {
      return null; // 如果根节点为空，返回 null 表示未找到目标节点
    }

    if (val === root.val) {
      return root; // 如果当前节点的值等于目标值，返回当前节点
    } else if (val < root.val) {
      return this.searchBST(root.left, val); // 如果目标值小于当前节点的值，继续在左子树中搜索
    } else {
      return this.searchBST(root.right, val); // 如果目标值大于当前节点的值，继续在右子树中搜索
    }
  }
}

// 创建一个二叉搜索树
const root = new TreeNode(4);
root.left = new TreeNode(2);
root.right = new TreeNode(7);
root.left.left = new TreeNode(1);
root.left.right = new TreeNode(3);

const solution = new Solution();
const targetValue = 3; // 要搜索的目标值
const result = solution.searchBST(root, targetValue);

console.log(result);

2. 二叉搜索树的插入

2.1. 思路

如果二叉搜索树为空，则创建一个值为 val 的节点，并将其作为二叉搜索树的根节点。

如果二叉搜索树不为空，则将待插入的值 val 与二叉搜索树根节点的值 root.val 进行比较：

如果 val < root.val，则递归将值为 val 的节点插入到左子树中。

如果 val > root.val，则递归将值为 val 的节点插入到右子树中

2.2. 代码

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

class Solution {
  insertIntoBST(root, val) {
    if (root === null) {
      return new TreeNode(val); // 如果根节点为空，直接创建一个包含目标值的新节点并返回
    }

    if (val < root.val) {
      root.left = this.insertIntoBST(root.left, val); // 如果目标值小于当前节点的值，在左子树中插入目标值
    } else if (val > root.val) {
      root.right = this.insertIntoBST(root.right, val); // 如果目标值大于当前节点的值，在右子树中插入目标值
    }

    return root; // 返回更新后的根节点
  }
}

// 创建一个二叉搜索树
const root = new TreeNode(4);
root.left = new TreeNode(2);
root.right = new TreeNode(7);
root.left.left = new TreeNode(1);
root.left.right = new TreeNode(3);

const solution = new Solution();
const newValue = 5; // 要插入的新值
const updatedRoot = solution.insertIntoBST(root, newValue);

console.log(updatedRoot); // 输出更新后的二叉搜索树

3. 二叉搜索树的创建

3.1. 思路

1. 初始化二叉搜索树为空树。
2. 遍历数组元素，将数组元素值 nums[i] 依次插入到二叉搜索树中。
3. 将数组中全部元素值插入到二叉搜索树中之后，返回二叉搜索树的根节点。

3.2. 代码

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

class Solution {
  // 插入节点到二叉搜索树的方法
  insertIntoBST(root, val) {
    if (root === null) {
      return new TreeNode(val); // 如果根节点为空，创建一个包含目标值的新节点并返回
    }

    if (val < root.val) {
      root.left = this.insertIntoBST(root.left, val); // 如果目标值小于当前节点的值，在左子树中插入目标值
    } else if (val > root.val) {
      root.right = this.insertIntoBST(root.right, val); // 如果目标值大于当前节点的值，在右子树中插入目标值
    }

    return root; // 返回更新后的根节点
  }

  // 从数组构建二叉搜索树的方法
  buildBST(nums) {
    let root = null; // 初始根节点为空
    for (const num of nums) {
      root = this.insertIntoBST(root, num); // 逐个插入数组中的值到二叉搜索树
    }
    return root; // 返回构建完成的二叉搜索树的根节点
  }
}

// 示例用法
const solution = new Solution();
const nums = [4, 2, 7, 1, 3];
const bst = solution.buildBST(nums);
console.log(bst); // 输出构建完成的二叉搜索树

4. 二叉搜索树的删除

4.1. 思路

1. 如果当前节点为空，则返回当前节点。
2. 如果当前节点值大于 val，则递归去左子树中搜索并删除，此时 root.left 也要跟着递归更新。
3. 如果当前节点值小于 val，则递归去右子树中搜索并删除，此时 root.right 也要跟着递归更新。
4. 如果当前节点值等于 val，则该节点就是待删除节点。

1. 1. 如果当前节点的左子树为空，则删除该节点之后，则右子树代替当前节点位置，返回右子树。
   2. 如果当前节点的右子树为空，则删除该节点之后，则左子树代替当前节点位置，返回左子树。
   3. 如果当前节点的左右子树都有，则将左子树转移到右子树最左侧的叶子节点位置上，然后右子树代替当前节点位置

4.2. 代码

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

class Solution {
  deleteNode(root, key) {
    if (!root) {
      return null; // 如果当前节点为空，返回 null
    }

    if (key < root.val) {
      // 如果待删除节点在左子树中
      root.left = this.deleteNode(root.left, key);
    } else if (key > root.val) {
      // 如果待删除节点在右子树中
      root.right = this.deleteNode(root.right, key);
    } else {
      // 当前节点就是待删除节点
      if (!root.left) {
        // 情况 1: 如果左子树为空，返回右子树
        return root.right;
      } else if (!root.right) {
        // 情况 2: 如果右子树为空，返回左子树
        return root.left;
      }

      // 情况 3: 左右子树都存在
      // 找到右子树中的最小值节点，将该节点的值复制给当前节点
      root.val = this.getMinValue(root.right);
      // 然后在右子树中递归删除最小值节点
      root.right = this.deleteNode(root.right, root.val);
    }

    return root;
  }

  getMinValue(root) {
    // 获取以 root 为根的二叉搜索树的最小值节点的值
    while (root.left) {
      root = root.left;
    }
    return root.val;
  }
}

// 创建一个二叉搜索树
const root = new TreeNode(5);
root.left = new TreeNode(3);
root.right = new TreeNode(6);
root.left.left = new TreeNode(2);
root.left.right = new TreeNode(4);
root.right.right = new TreeNode(7);

const solution = new Solution();
const keyToDelete = 3;
const updatedRoot = solution.deleteNode(root, keyToDelete);

console.log(updatedRoot);

——未完待续——