C++在无序树中查找具有最高值的节点

#include <iostream>
#include <vector>

struct TreeNode {
    int value;
    std::vector<TreeNode*> children;
};

// 递归实现的DFS算法
void dfs(TreeNode* node, int& maxValue, TreeNode*& maxNode) {
    if (node == nullptr) {
        return;
    }
    
    if (node->value > maxValue) {
        maxValue = node->value;
        maxNode = node;
    }
    
    for (TreeNode* child : node->children) {
        dfs(child, maxValue, maxNode);
    }
}

// 在无序树中查找具有最高值的节点
TreeNode* findMaxNode(TreeNode* root) {
    if (root == nullptr) {
        return nullptr;
    }
    
    int maxValue = INT_MIN;
    TreeNode* maxNode = nullptr;
    
    dfs(root, maxValue, maxNode);
    
    return maxNode;
}

int main() {
    // 构建一个无序树
    TreeNode* root = new TreeNode{10, {}};
    TreeNode* node1 = new TreeNode{5, {}};
    TreeNode* node2 = new TreeNode{8, {}};
    TreeNode* node3 = new TreeNode{3, {}};
    TreeNode* node4 = new TreeNode{12, {}};
    
    root->children.push_back(node1);
    root->children.push_back(node2);
    node1->children.push_back(node3);
    node2->children.push_back(node4);
    
    // 查找具有最高值的节点
    TreeNode* maxNode = findMaxNode(root);
    
    if (maxNode != nullptr) {
        std::cout << "具有最高值的节点为: " << maxNode->value << std::endl;
    } else {
        std::cout << "树为空" << std::endl;
    }
    
    // 释放内存
    delete node4;
    delete node3;
    delete node2;
    delete node1;
    delete root;
    
    return 0;
}