algo-aha

以下写法中，height是从叶节点往上的节点数，空节点为0、叶节点为1；depth与height不区分。 都不像教科书上的，height定义为离叶节点的边数，叶节点高度为0；depth定义为离根节点的边数，根节点深度为0。

满二叉树的节点数

• https://leetcode.com/problems/count-complete-tree-nodes/

int countNodes(TreeNode* root) {
    if (!root) return 0;
    int leftH = getHeight(root->left);
    int rightH = getHeight(root->right);
    if (leftH == rightH) { // 左子树是满二叉树，左子树和根节点共(2^leftH-1)+1
        return (1 << leftH) + countNodes(root->right);
    } else { // 右子树是满二叉树
        return (1 << rightH) + countNodes(root->left);
    }
}

int getHeight(TreeNode *root) {
    int height = 0;
    while (root) {
        height++;
        root = root->left;
    }
    return height;
}

把叶节点一遍遍剥离

• https://leetcode.com/problems/find-leaves-of-binary-tree/

先剥离高度为0的节点，再剥离高度为1的节点……

vector<vector<int>> findLeaves(TreeNode* root) {
    vector<vector<int>> ans;
    getHeight(root, ans);
    return ans;
}

int getHeight(TreeNode *root, vector<vector<int>> &ans) {
    // 高h节点放到ans[h]中，让叶节点高为0，故定义空节点高为-1
    if (!root) return -1;
    auto left = getHeight(root->left, ans);
    auto right = getHeight(root->right, ans);
    int h = 1 + max(left, right);
    
    if (h == ans.size()) ans.push_back({});
    ans[h].push_back(root->val);
    return h;
}

无向图的哪些节点提作树中心，可使树高度最小

• https://leetcode.com/problems/minimum-height-trees/

vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
    // 叶节点到这些“根”的距离最长，从外往内一圈圈删除叶节点，最后剩下的可作为根。
    // bfs不断删除度为1的叶节点，根据最长路径的奇偶性，可能剩下1个或2个节点。
    vector<vector<int>> adj(n);
    for (auto &edge : edges) {
        adj[edge[0]].push_back(edge[1]);
        adj[edge[1]].push_back(edge[0]);
    }
    vector<int> leaves;
    vector<int> degree(n);
    for (int i = 0; i < n; i++) {
        degree[i] = adj[i].size();
        if (degree[i] == 0 || degree[i] == 1) { // 单个节点的度为0
            leaves.push_back(i);
            degree[i] = 0; // 删除叶节点
        }
    }
    
    int count = leaves.size();
    while (count < n) {
        vector<int> newLeaves;
        for (int u : leaves) {
            for (int v : adj[u]) {
                if (--degree[v] == 1) newLeaves.push_back(v);
            }
            degree[u] = 0; // 删除叶节点
        }
        swap(leaves, newLeaves);
        count += leaves.size();
    }
    return leaves;
}