Phần tử lớn hơn tiếp theo trong cây N-ary C++

Cho cây N-ary (mỗi nút có nhiều con) và số x. Tìm giá trị nhỏ nhất trong cây mà > x (next greater element).

Thuật toán DFS

• Duyệt đệ quy toàn cây.
• Giữ biến result (con trỏ nút) khởi tạo NULL.
• Khi gặp nút data > x:
  • Nếu result == NULL hoặc data < result->data → cập nhật result.

Triển khai C++

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

struct Node {
    int data;
    vector child;
};

Node* newNode(int data) {
    Node* n = new Node;
    n->data = data;
    return n;
}

void findNextGreater(Node* root, int x, Node** result) {
    if (!root) return;
    if (root->data > x) {
        if (!*result || (*result)->data > root->data)
            *result = root;
    }
    for (Node* c : root->child)
        findNextGreater(c, x, result);
}

int main() {
    Node* root = newNode(10);
    root->child = {newNode(12), newNode(23), newNode(45)};
    root->child[0]->child.push_back(newNode(40));
    root->child[1]->child.push_back(newNode(33));
    root->child[2]->child.push_back(newNode(12));

    Node* res = nullptr;
    findNextGreater(root, 20, &res);
    cout << res->data << endl; // 23
    return 0;
}

Kết quả

23