[Algo] 二叉树常见题目

1. 层序遍历

// 1. 层序遍历
void BFS(BinaryTreeNode *root)
{
    queue<BinaryTreeNode *> q;
    vector<BinaryTreeNode *> v;
    q.push(root);
    while (!q.empty())
    {
        while (!q.empty())
        {
            v.push_back(q.front());
            q.pop();
        }
        for (auto e : v)
        {
            cout << e->val << " ";
            if (e->left) q.push(e->left);
            if (e->right) q.push(e->right);
        }
        cout << endl;
        v.clear();
    }
}

2. 最大深度和最小深度

int maxDepth(BinaryTreeNode *root)
{
    return root == nullptr ? 0 : max(maxDepth(root->left), maxDepth(root->right)) + 1;
}

int minDepth(BinaryTreeNode *root)
{
    // 最小深度必须以叶节点作为结束
    if (root == nullptr) return 0;
    if (root->left == nullptr && root->right == nullptr) return 1;
    if (root->left == nullptr) return minDepth(root->right) + 1;
    if (root->right == nullptr) return minDepth(root->left) + 1;
    return min(minDepth(root->right), minDepth(root->left)) + 1;
}

3. 序列化与反序列化(先序)

string preOrderSerialize(BinaryTreeNode *root)
{
    if (root == nullptr) return "#,";
    return to_string(root->val) + "," + preOrderSerialize(root->left) + preOrderSerialize(root->right);
}

int curIndex = 0; // 全局遍历记录当前位置
BinaryTreeNode *preOrderDeserialize(const string &s)
{
    if (s[curIndex] == '#') { curIndex += 2; return nullptr; }
    string val_str = "";
    while (s[curIndex] != ',') val_str += s[curIndex++];
    curIndex++;
    BinaryTreeNode *root = new BinaryTreeNode(stoi(val_str));
    root->left = preOrderDeserialize(s);
    root->right = preOrderDeserialize(s);
    return root;
}

4. 由先序序列和中序序列构建二叉树

BinaryTreeNode *construct(const vector<int> &pre, int l1, int r1, const vector<int> &in, int l2, int r2, const unordered_map<int, int> &indexMap);
BinaryTreeNode *constructFromPreAndIn(const vector<int> &pre, const vector<int> &in)
{
    unordered_map<int, int> indexMap;
    for (int i = 0; i < in.size(); i++) indexMap[in[i]] = i; // 快速获取值在中序序列的位置，用于加速
    return construct(pre, 0, pre.size() - 1, in, 0, in.size() - 1, indexMap);
}
BinaryTreeNode *construct(const vector<int> &pre, int l1, int r1, const vector<int> &in, int l2, int r2, const unordered_map<int, int> &indexMap)
{
    if (l1 > r1) return nullptr;
    if (l1 == r1) return new BinaryTreeNode(pre[l1]);
    int k = indexMap.at(pre[l1]);
    BinaryTreeNode *root = new BinaryTreeNode(pre[l1]);
    root->left = construct(pre, l1 + 1, l1 + k - l2, in, l2, k - 1, indexMap);
    root->right = construct(pre, l1 + k - l2 + 1, r1, in, k + 1, r2, indexMap);
    return root;
}

5. 判断是否是完全二叉树

bool isCompleteTree(BinaryTreeNode *root)
{
    queue<BinaryTreeNode *> q;
    queue<int> index;
    int lastIndex = 0;
    q.push(root);
    index.push(1);
    while (!q.empty())
    {
        BinaryTreeNode *e = q.front();
        int curIndex = index.front();
        if (curIndex != lastIndex + 1) return false; 
        lastIndex = curIndex;
        q.pop();
        index.pop();
        if (e->left) { q.push(e->left); index.push(2 * curIndex); }
        if (e->right) { q.push(e->right); index.push(2 * curIndex + 1); }
    }
    return true;
}

6. 完全二叉树节点数

int heightBCT(BinaryTreeNode *root);
int countBCT(BinaryTreeNode *root)
{
    int height = heightBCT(root);
    if (height == 0) return 0;
    int right_height = heightBCT(root->right);
    if (right_height == height - 1) return countBCT(root->right) + (1 << right_height);
    else return countBCT(root->left) + (1 << right_height);
}
int heightBCT(BinaryTreeNode *root)
{
    int ans = 0;
    while (root != nullptr) { root = root->left; ans++; }
    return ans;
}