通用搜索树findKeyHelper递归无法完成跨子树遍历问题求解

• 递归返回值断裂：所有分支的递归调用都没有用return承接结果。哪怕深层递归找到了匹配节点，当前栈帧也不会把结果向上传递，会直接走到函数末尾触发未定义行为，根本拿不到查找结果；且原代码未对入参currNode做空指针校验，一旦递归传入空值就会直接触发非法内存访问崩溃。
• 遍历路径无回溯：代码只要检测到当前节点存在子节点，就直接进入第一个子节点的子树遍历；等这棵子树完全穷尽、没有匹配目标时，没有逻辑引导流程回到父节点层级，自然不会去搜索同层其他兄弟节点挂接的未遍历子树，会漏掉大量搜索分支。

核心逻辑遵循前序搜索的规则，保证每一层遍历都能在单棵子树穷尽后自动流转到下一个待搜索分支：

• 首先增加空节点边界保护，从根源规避空指针访问问题
• 优先校验当前节点的键值，匹配则直接返回对应节点指针
• 当前节点不匹配时，先从第一个子节点开始递归，搜完所有子节点构成的完整子树，只要任意分支返回匹配结果，就直接把结果向上传递
• 所有子树遍历完成仍未找到目标时，再顺着当前节点的兄弟节点链，递归搜索同层其他分支
• 整条搜索路径全部走完仍无匹配，才返回空指针

调整后的参考实现：

shared_ptr<node<T,S>> Tree<T,S>::findKeyHelper(shared_ptr<node<T,S>> currNode, T key) {
    // 空节点直接返回，规避空指针访问问题
    if (!currNode) return nullptr;

    // 当前节点命中目标键直接返回
    if (currNode->key == key) {
        return currNode;
    }

    shared_ptr<node<T,S>> searchResult = nullptr;
    // 先搜索当前节点的所有子树，从第一个child开始递归
    if (currNode->child) {
        searchResult = findKeyHelper(currNode->child, key);
    }
    // 子树没找到匹配，再沿着兄弟节点链搜索同层其他分支
    if (!searchResult && currNode->sibling) {
        searchResult = findKeyHelper(currNode->sibling, key);
    }
    // 把当前层的搜索结果逐层向上传递
    return searchResult;
}

上述实现的遍历顺序为「当前节点 → 全部子树 → 同层兄弟节点分支」，每一层搜索都会在单棵子树遍历完成、未命中目标时，自动流转到下一个待搜索分支，不会出现进入第一棵子树就不回头、漏搜其他子树的问题。

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