Nút nhỏ thứ hai trong cây nhị phân đặc biệt trong C++

Mô tả bài toán

Cho cây nhị phân đặc biệt: mỗi nút có 0 hoặc 2 con, và giá trị nút = min(giá trị con trái, con phải). Tìm giá trị nhỏ thứ hai trong tập giá trị tất cả nút. Nếu không có, trả về -1.

Ví dụ: Cây gốc 2, con trái 2, con phải 5, tiếp theo 5 và 7 → Giá trị nhỏ nhất 2, nhỏ thứ hai 5.

Giải pháp (Duyệt cây)

• Giá trị nhỏ nhất = giá trị gốc (do tính chất cây).
• Duyệt toàn cây (DFS), tìm giá trị nhỏ nhất > giá trị gốc.
• Cập nhật nextMin khi thấy giá trị thỏa mãn.

Ví dụ minh họa

#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) { temp->left = val ? new TreeNode(val) : new TreeNode(0); return; }
        else q.push(temp->left);
        if (!temp->right) { temp->right = val ? new TreeNode(val) : 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;
}

class Solution {
public:
    int findSecondMinimumValue(TreeNode* root) {
        int min = (root && root->val != 0) ? root->val : -1;
        int nextMin = -1;
        TraverseNodes(root, min, nextMin);
        return nextMin;
    }
    void TraverseNodes(TreeNode* node, int min, int& nextMin) {
        if (!node || node->val == 0) return;
        if (node->val > min) {
            if (nextMin == -1 || node->val < nextMin) nextMin = node->val;
        }
        TraverseNodes(node->left, min, nextMin);
        TraverseNodes(node->right, min, nextMin);
    }
};

int main() {
    Solution ob;
    vector<int> v = {2,2,5,0,0,5,7}; // NULL dùng 0
    TreeNode* root = make_tree(v);
    cout << ob.findSecondMinimumValue(root);
    return 0;
}

Đầu vào

{2,2,5,NULL,NULL,5,7}

Đầu ra

5