算法模板--树

1.二叉树

• 不要思考整体，聚焦局部，考虑单独抽出一个二叉树节点需要做什么
• 明确递归函数定义，并利用定义

1. 遍历 不用返回值，利用全局变量更新结果

void traverse(TreeNode root) {
    if (root == null) {
        return;
    }
    // 前序位置
    traverse(root.left);
    // 中序位置
    traverse(root.right);
    // 后序位置
}

2. 分解问题 通过子树推导，利用函数定义和返回（只有后序位置才能通过返回值获取子树的信息）

一旦发现题目和子树有关，那大概率要给函数设置合理的定义和返回值，在后序位置写代码了。

// 定义：输入一棵二叉树，返回这棵二叉树的节点总数
int count(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int leftCount = count(root.left);
    int rightCount = count(root.right);
    // 后序位置
    printf("节点 %s 的左子树有 %d 个节点，右子树有 %d 个节点",
            root, leftCount, rightCount);

    return leftCount + rightCount + 1;
}

2.DFS（属于遍历问题，关注单个节点）

void backtrack(...) {
    if (到达叶子节点) {
        return;
    }

    做选择
    ...
    for (int i = 0, i < n; i++) {
        backtrack(...)
    }
    撤销选择
    ...
}

3.字典树

    int N = 300010;
    int[][] son = new int[N][26]; // 儿子的位置 = son[父亲的位置][儿子的名字];
    int idx = 0; // 全局编号
    int[] cnt = new int[N]; // 记录字符串个数

    // 插入
    public void insert(String word) {
        int p = 0; // 节点指针
        for (int i = 0; i < word.length(); i++){
            int u = word.charAt(i) - 'a';
            if (son[p][u] == 0)
                son[p][u] = ++idx;
            p = son[p][u];
        }
        cnt[p]++; // 个数增加
    }
    // 查找是否存在
    public boolean search(String word) {
        int p = 0;
        for (int i = 0; i < word.length(); i++){
            int u = word.charAt(i) - 'a';
            if (son[p][u] == 0)
                return false; 
            p = son[p][u];
        }
        return cnt[p] != 0;
    }
    
    // 查找是否是前缀
    public boolean startsWith(String prefix) {
        int p = 0;
        for (int i = 0; i < prefix.length(); i++){
            int u = prefix.charAt(i) - 'a';
            if (son[p][u] == 0)
                return false; 
            p = son[p][u];
        }
        return true;
    }

4.并查集

应用：将两个集合合并、询问两个元素是否在一个集合中

class UnionFind {
    int[] parents;

    public UnionFind(int totalNodes) { // 初始化
        parents = new int[totalNodes];
        for (int i = 0; i < totalNodes; i++) {
            parents[i] = i;
        }
    }
	// 合并两个元素
    void union(int node1, int node2) {
        int root1 = find(node1);
        int root2 = find(node2);
        if (root1 != root2) {
            parents[root2] = root1;
        }
    }
    // 返回元素的祖宗节点
    int find(int node) {
        if (parents[node] != node){
            parents[node] = find(parents[node]);
        }
        return parents[node];
    }
    // 判断是否在统一集合中
    boolean isConnected(int node1, int node2) {
        return find(node1) == find(node2);
    }
}