Cây con nhỏ nhất chứa tất cả nút sâu nhất trong C++

Cho cây nhị phân gốc root, độ sâu nút = khoảng cách đến gốc. Nút "sâu nhất" có độ sâu lớn nhất. Tìm nút sâu nhất sao cho cây con gốc tại nút đó chứa tất cả nút sâu nhất.

Ví dụ: cây {3,5,1,6,2,0,8,null,null,7,4} → Cây con gốc tại nút 2 (chứa 7,4).

Giải thuật (DFS pós-order)

1. Hàm solve(root) trả về cặp (nút gốc cây con chứa tất cả lá sâu nhất, độ sâu lớn nhất).
2. Nếu root null → (null, 0).
3. L = solve(left), R = solve(right).
4. Nếu L.second > R.second → trả (L.first, L.second+1).
5. Nếu L.second < R.second → trả (R.first, R.second+1).
6. Nếu bằng nhau → trả (root, L.second+1) (nút hiện tại là LCA của các lá sâu nhất).

Ví dụ C++

#include <bits/stdc++.h>
using namespace std;

class TreeNode {
public:
    int val; TreeNode *left, *right;
    TreeNode(int data) { val = data; left = right = NULL; }
};

void insert(TreeNode **root, int val) {
    queue<TreeNode*> q; q.push(*root);
    while(q.size()) {
        TreeNode *temp = q.front(); q.pop();
        if(!temp->left) {
            if(val != NULL) temp->left = new TreeNode(val);
            else temp->left = new TreeNode(0); return;
        } else q.push(temp->left);
        if(!temp->right) {
            if(val != NULL) temp->right = new TreeNode(val);
            else temp->right = new TreeNode(0); return;
        } else q.push(temp->right);
    }
}

TreeNode *make_tree(vector<int> v) {
    TreeNode *root = new TreeNode(v[0]);
    for(int i = 1; i < v.size(); i++) insert(&root, v[i]);
    return root;
}

void tree_level_trav(TreeNode* root) {
    if(!root) return;
    cout << "[";
    queue<TreeNode*> q; q.push(root); q.push(NULL);
    while(q.size() > 1) {
        TreeNode* curr = q.front(); q.pop();
        if(curr == NULL) q.push(NULL);
        else {
            if(curr->left) q.push(curr->left);
            if(curr->right) q.push(curr->right);
            if(curr->val == 0) cout << "null, ";
            else cout << curr->val << ", ";
        }
    }
    cout << "]" << endl;
}

class Solution {
public:
    pair<TreeNode*, int> solve(TreeNode* root) {
        if(!root || root->val == 0) return {NULL, 0};
        auto L = solve(root->left);
        auto R = solve(root->right);
        if(L.second > R.second) return {L.first, L.second + 1};
        else if(L.second < R.second) return {R.first, R.second + 1};
        return {root, L.second + 1};
    }
    TreeNode* subtreeWithAllDeepest(TreeNode* root) {
        return solve(root).first;
    }
};

int main() {
    vector<int> v = {3,5,1,6,2,0,8,NULL,NULL,7,4};
    TreeNode *root = make_tree(v);
    Solution ob;
    tree_level_trav(ob.subtreeWithAllDeepest(root));
    return 0;
}

Đầu vào

{3,5,1,6,2,0,8,NULL,NULL,7,4}

Đầu ra

[2,7,4]