Algorithms.md

Morris 遍历

优势

仅用常数空间实现对一棵二叉树的遍历。

核心思想

寻找当前节点的前驱节点，判断前驱节点的右节点是否为当前节点，若否则证明还未遍历左子树，将前驱节点的右节点指向当前节点，若是则证明当前节点的左子树全部遍历完成。

实现思路

• 前序遍历
  1. 新建一个当前节点指向 root 节点；
  2. 如果当前节点的左节点为空，输出当前节点，并将其右节点置为新的当前节点；
  3. 如果当前节点的左节点非空，寻找当前节点的前驱节点：
     • 如果前驱节点的右节点为空，将其指向当前节点，输出当前节点，并将当前节点的左节点置为新的当前节点；
     • 如果前驱节点的右节点非空（意味着前驱节点的右节点为当前节点，当前节点的左子树已经全部遍历完成），将其右节点置空（还原二叉树），并将当前节点的右节点置为新的当前节点。
  4. 重复步骤 2-3 至当前节点为空。
• 中序遍历
  1. 新建一个当前节点指向 root 节点；
  2. 如果当前节点的左节点为空，输出当前节点，并将其右节点置为新的当前节点；
  3. 如果当前节点的左节点非空，寻找当前节点的前驱节点：
     • 如果前驱节点的右节点为空，将其指向当前节点，并将当前节点的左节点置为新的当前节点；
     • 如果前驱节点的右节点非空，将其右节点置空，输出当前节点，并将当前节点的右节点置为新的当前节点。
  4. 重复步骤 2-3 至当前节点为空。
• 后序遍历
  1. 新建一个临时节点，并令该节点的左节点指向 root 节点；
  2. 如果当前节点的左节点为空，将其右节点置为新的当前节点；
  3. 如果当前节点的左节点非空，寻找当前节点的前驱节点：
     • 如果前驱节点的右节点为空，将其指向当前节点，并将当前节点的左节点置为新的当前节点；
     • 如果前驱节点的右节点非空，倒序输出当前节点左节点到前驱节点，将前驱节点的右节点置空，并将当前节点的右节点置为新的当前节点。
  4. 重复步骤 2-3 至当前节点为空。

相关题目

1. 前序遍历：https://leetcode-cn.com/problems/binary-tree-preorder-traversal/

红黑树

基本性质

1. 节点分为红色或者黑色；
2. 根节点必为黑色；
3. 叶子节点都为黑色，且为null；
4. 连接红色节点的两个子节点都为黑色（红黑树不会出现相邻的红色节点）；
5. 从任意节点出发，到其每个叶子节点的路径中包含相同数量的黑色节点；
6. 新加入到红黑树的节点为红色节点。
   • 不加黑色节点的原因：从根节点到叶子节点的黑色节点数相同，加入黑色节点必定会破坏性质。

隐藏信息

1. 从根节点到叶子节点的最长路径不大于最短路径的2倍。
   • 最长路径为红黑节点交替的路径，最短路径为全黑节点路径。

左旋和右旋

• 左旋：将根节点作为新左节点，右节点作为新根，右节点的左节点作为新左节点的右节点。
• 右旋：将根节点作为新右节点，左节点作为新根，左节点的右节点作为新右节点的左节点。

插入操作

• 无需调整
  1. 当父节点为黑色节点时。
• 变色
  1. 空树插入（将根节点变黑）；
  2. 父节点和叔父节点都为红色。
• 旋转 + 变色（父节点为红，叔父节点为黑）
  • 父节点为左节点
    • 插入节点为左节点：右旋父节点
    • 插入节点为右节点：左旋父节点，右旋祖父节点
  • 父节点为右节点
    • 插入节点为右节点：左旋父节点
    • 插入节点为左节点：右旋父节点，左旋祖父节点
  • 统一的变色操作：将旋转后的树的根节点变为黑色（为了不破坏上层树的性质），其子节点变为红色。

删除操作

• 删除的是根节点，则直接将根节点置为 null；
• 待删除节点的左右子节点都为 null，删除时将该节点置为 null；
• 待删除节点的左右子节点有一个有值，则用有值的节点替换该节点即可；
• 待删除节点的左右子节点都不为 null，则找前驱或者后继，将前驱或者后继的值复制到该节点中，然后删除前驱或者后继；
• 节点删除后可能会造成红黑树的不平衡，需通过变色和旋转来调整。