查找

排序

树寻找前驱算法

  1. class Solution {
  2.     public void flatten(TreeNode root) {
  3.         TreeNode curr = root;
  4.         while (curr != null) {
  5.             if (curr.left != null) {
  6.                 TreeNode next = curr.left;
  7.                 TreeNode predecessor = next;
  8.                 while (predecessor.right != null) {
  9.                     predecessor = predecessor.right;
  10.                 }
  11.                 predecessor.right = curr.right;
  12.                 curr.left = null;
  13.                 curr.right = next;
  14.             }
  15.             curr = curr.right;
  16.         }
  17.     }
  18. }

Morris遍历

用于实现二叉树的遍历，节省内存空间，利用叶节点的左右孩子指向遍历的钱去或者后驱的节点，指针叫做线索，实现线索二叉树
前序遍历：根结点 —-> 左子树 —-> 右子树
中序遍历：左子树—-> 根结点 —-> 右子树
后序遍历：左子树 —-> 右子树 —-> 根结点

中序遍历流程

  1. 当前节点左孩子是否为空，是则输出当前节点，更新当前节点为前节点的右孩子，否则进入2；

  2. 在当前节点的柚子树中寻找中序遍历下的前驱节点，（左子树的最右节点）

    1. 若前驱节点右孩子为空则将前驱节点的右孩子指向当前节点，当前节点更新为左孩子
    2. 若前驱节点的右孩子为当前节点（不为空），则将前驱节点的
      1. cur = root
      2. repeat until cur != NULL:
      3. if cur.left != NULL:
      4.   pre = cur.left;
      5.   while pre.right == NULL && pre.right != cur://找到前驱结点pre
      6.       pre = pre.right
      7.   if pre.right == NULL:
      8.       pre.right = cur
      9.       cur = cur.left
      10.   else:
      11.       print(cur)
      12.       pre.right = NULL
      13.       cur = cur.right
      14. else:
      15.   print(cur)
      16.   cur = cur.right

      前序遍历流程

  3. 当前结点的左孩子是否为空，若是则输出当前结点，并更新当前结点为当前结点的右孩子；否则进入2；

  4. 在当前结点的左子树中寻找中序遍历下的前驱结点（左子树中最右结点）

a. 若前驱结点的右孩子为空，则将前驱结点的右孩子指向当前结点，输出当前结点（在这里输出，和中序遍历不同的地方），当前结点更新为当前结点的左孩子；进入3；
b. 若前驱结点的右孩子为当前结点（不为空），将前驱结点的右孩子置NULL，当前结点更新为当前结点的右孩子，进入3；

  1. cur = root;
  2. repeat until cur != NULL:
  3.     if cur.left != NULL:
  4.         pre = cur.left;
  5.         while pre.right == NULL && pre.right != cur://找到前驱结点pre
  6.             pre = pre.right
  7.         if pre.right == NULL:
  8.             pre.right = cur
  9.             print(cur)//此处和中序遍历不同
  10.             cur = cur.left
  11.         else:
  12.             pre.right = NULL
  13.             cur = cur.right
  14.     else:
  15.         print(cur)
  16.         cur = cur.right

后序遍历流程

  1. 新建一个Dummy结点，该结点的左孩子指向树根root，将Dummy作为当前结点；
  2. 当前结点的左孩子是否为空，更新当前结点为当前结点的右孩子；否则进入2；
  3. 在当前结点的左子树中寻找中序遍历下的前驱结点（左子树中最右结点）：

a. 若前驱结点的右孩子为空，则将前驱结点的右孩子指向当前结点，当前结点更新为当前结点的左孩子，进入3；
b. 若前驱结点的右孩子为当前结点（不为空），反转当前结点到前驱结点之间的路径，输出该路径所有结点；反转当前结点到前驱结点之间的路径，恢复原状。将前驱结点的右孩子置NULL，当前结点更新为当前结点的右孩子；

  1. public class Singleton {  
  2.     private volatile static Singleton singleton;  
  3.     private Singleton (){}  
  4.     public static Singleton getSingleton() {  
  5.     if (singleton == null) {  
  6.         synchronized (Singleton.class) {  
  7.         if (singleton == null) {  
  8.             singleton = new Singleton();  
  9.         }  
  10.         }  
  11.     }  
  12.     return singleton;  
  13.     }  
  14. }

查并集

  1. /* 并查集模板 */
  2. class UnionFind {
  3. public:
  4.     vector<int> parent;
  5.     vector<int> size;
  6.     int n;
  7.     // 当前连通分量数目
  8.     int setCount;
  9. public:
  10.     UnionFind(int _n): n(_n), setCount(_n), parent(_n), size(_n, 1) {
  11.         iota(parent.begin(), parent.end(), 0);  /* 赋值0-n-1 */
  12.     }
  14.     int findset(int x) {
  15.         return parent[x] == x ? x : parent[x] = findset(parent[x]);
  16.     }
  18.     bool unite(int x, int y) {
  19.         x = findset(x);
  20.         y = findset(y);
  21.         if (x == y) {
  22.             return false;
  23.         }
  24.         if (size[x] < size[y]) {
  25.             swap(x, y);
  26.         }
  27.         parent[y] = x;
  28.         size[x] += size[y];
  29.         --setCount;
  30.         return true;
  31.     }
  33.     bool connected(int x, int y) {
  34.         x = findset(x);
  35.         y = findset(y);
  36.         return x == y;
  37.     }
  38. };