面试题：C++ 实现基于二叉树的复杂查询优化

算法思路：
- 采用前缀和的思想。对于二叉树中的每一条从根节点到叶节点的路径，记录路径上节点值的前缀和。
- 对于每个节点，从该节点出发的路径和可以通过计算从根节点到该节点路径上的前缀和差值得到。
- 使用哈希表来存储前缀和及其出现的次数，这样在遍历到某节点时，可以快速查询到是否存在前缀和使得当前路径和为目标值。
代码实现：

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

struct BigTreeNode {
    int data;
    BigTreeNode* left;
    BigTreeNode* right;
    BigTreeNode(int x) : data(x), left(nullptr), right(nullptr) {}
};

class Solution {
private:
    vector<vector<int>> result;
    vector<int> currentPath;
    unordered_map<int, int> prefixSumCount;

    void findPaths(BigTreeNode* node, int currentSum, int targetSum) {
        if (!node) return;

        currentSum += node->data;
        // 如果当前和减去目标和在哈希表中存在，说明找到了一条路径
        if (prefixSumCount.find(currentSum - targetSum) != prefixSumCount.end()) {
            for (int i = 0; i < prefixSumCount[currentSum - targetSum]; ++i) {
                result.push_back(currentPath);
            }
        }
        prefixSumCount[currentSum]++;
        currentPath.push_back(node->data);

        findPaths(node->left, currentSum, targetSum);
        findPaths(node->right, currentSum, targetSum);

        // 回溯
        currentPath.pop_back();
        prefixSumCount[currentSum]--;
    }

public:
    vector<vector<int>> findPathsWithSum(BigTreeNode* root, int targetSum) {
        prefixSumCount[0] = 1;
        findPaths(root, 0, targetSum);
        return result;
    }
};

时间复杂度分析：
- 对于每个节点，我们只遍历一次，在每个节点处，哈希表的操作（插入和查询）时间复杂度为 $O(1)$。
- 因此，总的时间复杂度为 $O(n)$，其中 $n$ 是二叉树的节点数。
空间复杂度分析：
- 哈希表中最多可能存储从根节点到叶节点最长路径上的前缀和，在最坏情况下，二叉树是一条链，此时哈希表的空间复杂度为 $O(h)$，其中 $h$ 是树的高度。
- 递归调用栈的空间复杂度也是 $O(h)$。
- 因此，总的空间复杂度为 $O(h)$。

优化思路：

这里已经采用了前缀和优化，避免了暴力遍历中重复计算路径和的问题。对于百万级别的节点，由于哈希表操作常数时间，并且每个节点仅遍历一次，已经是比较高效的方法。
如果树是平衡二叉树，高度 $h = O(\log n)$，时间和空间复杂度都能得到较好的保证；对于不平衡二叉树（最坏情况为一条链），可以考虑先对树进行一定的预处理（如平衡化操作），但这可能会增加额外的时间和空间开销，需要根据实际情况权衡。

星途面试题库

面试题：C++ 实现基于二叉树的复杂查询优化

知识考点

面试题答案