面试题：C++复杂递归场景下指针的内存安全与性能优化

Question

给定一个不规则的树状结构，节点定义如下：struct TreeNode { int data; TreeNode** children; int childCount; }; 编写一个递归函数，该函数接收根节点指针，计算整棵树所有节点data值的乘积。要求在递归过程中要确保指针使用的内存安全性，同时考虑性能优化，避免不必要的内存访问和递归深度过深导致的栈溢出问题，并且合理管理动态分配的内存。

Answer 1

#include <iostream>

struct TreeNode {
    int data;
    TreeNode** children;
    int childCount;
    TreeNode(int val) : data(val), children(nullptr), childCount(0) {}
    ~TreeNode() {
        if (children) {
            for (int i = 0; i < childCount; ++i) {
                delete children[i];
            }
            delete[] children;
        }
    }
};

long long calculateProduct(TreeNode* root) {
    if (!root) {
        return 1;
    }
    long long product = root->data;
    if (root->children) {
        for (int i = 0; i < root->childCount; ++i) {
            product *= calculateProduct(root->children[i]);
        }
    }
    return product;
}

你可以使用以下方式调用这个函数：

int main() {
    // 构建树状结构
    TreeNode* root = new TreeNode(2);
    root->childCount = 2;
    root->children = new TreeNode*[2];
    root->children[0] = new TreeNode(3);
    root->children[0]->childCount = 1;
    root->children[0]->children = new TreeNode*[1];
    root->children[0]->children[0] = new TreeNode(4);
    root->children[1] = new TreeNode(5);

    long long result = calculateProduct(root);
    std::cout << "整棵树所有节点data值的乘积: " << result << std::endl;

    delete root;
    return 0;
}

1. 节点内存释放：在TreeNode的析构函数中，我们首先检查children指针是否为空。如果不为空，遍历children数组，删除每个子节点，然后释放children数组本身。这样确保了在对象销毁时动态分配的内存得到正确释放。
2. 递归计算乘积：calculateProduct函数递归地计算树中所有节点data值的乘积。首先处理空节点的情况，返回1（乘法的单位元）。然后计算当前节点data与所有子节点乘积的乘积。
3. 避免栈溢出：虽然这里没有直接实现尾递归优化（C++标准并不强制要求编译器对尾递归进行优化），但是在实际应用中，可以通过手动模拟栈的方式将递归转换为迭代，从而避免栈溢出问题。
4. 性能优化：通过减少不必要的内存访问，例如在访问children数组之前先检查children指针是否为空，减少了潜在的空指针访问风险，同时也提高了性能。