LeetCode 2096题提交遇内存超限问题求助

你的代码在LeetCode上触发内存超限，核心问题出在递归逻辑和内存使用方式上：

问题根源 #

1. 递归无终止分支：在direct函数中，找到目标节点后，后续的左、右子树及父节点方向的递归仍会继续执行，产生大量无效递归调用，持续占用栈内存。
2. 字符串拷贝开销过高：每次递归传递path+"L"这类拼接后的字符串时，都会生成新的字符串副本，对于深度大的二叉树，这种累积拷贝会快速消耗内存。
3. 全局变量的使用虽不是直接原因，但容易导致多测试用例下的状态残留，增加调试复杂度。

修复后的代码 #

class Solution {
public:
    string getDirections(TreeNode* root, int startValue, int destValue) {
        unordered_map<TreeNode*, TreeNode*> parent;
        TreeNode* startNode = nullptr;
        
        // 遍历树记录父节点，定位起始节点
        function<void(TreeNode*)> dfsParent = [&](TreeNode* node) {
            if (!node) return;
            if (node->val == startValue) startNode = node;
            if (node->left) {
                parent[node->left] = node;
                dfsParent(node->left);
            }
            if (node->right) {
                parent[node->right] = node;
                dfsParent(node->right);
            }
        };
        
        dfsParent(root);
        
        string path;
        bool found = false;
        
        // 带终止标记的回溯找路径
        function<void(TreeNode*, TreeNode*)> dfsPath = [&](TreeNode* node, TreeNode* prev) {
            if (!node || found) return;
            if (node->val == destValue) {
                found = true;
                return;
            }
            // 尝试左子树
            if (node->left != prev) {
                path += 'L';
                dfsPath(node->left, node);
                if (found) return;
                path.pop_back();
            }
            // 尝试右子树
            if (node->right != prev) {
                path += 'R';
                dfsPath(node->right, node);
                if (found) return;
                path.pop_back();
            }
            // 尝试父节点
            if (parent.find(node) != parent.end()) {
                path += 'U';
                dfsPath(parent[node], node);
                if (found) return;
                path.pop_back();
            }
        };
        
        dfsPath(startNode, nullptr);
        return path;
    }
};

关键优化点 #

• 替换map为unordered_map：哈希表的查找和插入效率更高，内存占用更低。
• 加入递归终止标记found：一旦找到目标节点，立即终止所有后续递归，避免无效计算。
• 回溯法管理路径：通过引用传递字符串+回溯（pop_back），避免每次递归生成新字符串副本，大幅减少内存消耗。
• 移除全局变量：改用局部变量和lambda捕获，避免多测试用例下的状态残留，代码更健壮。

内容的提问来源于stack exchange，提问作者Ayush