后序递归深度优先搜索（DFS）查找节点返回异常问题求助

嘿，咱们来揪出这个后序遍历查找函数的核心问题！

你遇到的情况，本质是递归调用时没有传递子树的查找结果——哪怕左/右子树已经找到了目标节点，这个结果也被直接丢弃了，函数会继续执行后续的遍历逻辑。更糟的是，原函数最后如果没匹配到当前节点，连明确的返回值都没有，这属于C++里的未定义行为，你看到返回根节点其实是栈里的残留值在“捣乱”。

至于你觉得前序、中序函数正常，其实它们也藏着同样的潜在bug——只是你的测试用例刚好让目标节点的位置“掩盖”了问题（比如目标在根节点，或者遍历顺序中刚好在当前节点判断前就触发了返回）。

修复后的后序遍历函数 #

我们需要在递归调用左、右子树时，立即检查返回结果：如果子调用找到了目标，就直接把结果返回上去，不用再执行后续遍历。

template<typename T> inline typename BST<T>::Node* BST<T>::depth_first_postorder_s(Node* root,T x) {
    //若根节点为空
    if (!root) return nullptr;
    
    // 先遍历左子树，接收返回结果
    Node* left_result = depth_first_postorder_s(root->left,x);
    if (left_result != nullptr) {
        return left_result; // 左子树找到目标，直接返回
    }
    
    // 再遍历右子树，接收返回结果
    Node* right_result = depth_first_postorder_s(root->right,x);
    if (right_result != nullptr) {
        return right_result; // 右子树找到目标，直接返回
    }
    
    // 最后检查当前节点
    if (root->data == x) {
        return root;
    }
    
    // 所有情况都没找到，返回nullptr
    return nullptr;
}

顺便修正前序和中序函数的潜在问题 #

为了让这两个函数真正健壮，也需要做类似修改，确保子树的查找结果能正确传递：

修正后的前序遍历函数 #

template<typename T> inline typename BST<T>::Node* BST<T>::depth_first_preorder_s(Node* root,T x) {
    //若根节点为空
    if (!root) return nullptr;
    
    // 先检查当前节点
    if (root->data == x) {
        return root;
    }
    
    // 遍历左子树，找到则返回
    Node* left_result = depth_first_preorder_s(root->left,x);
    if (left_result != nullptr) {
        return left_result;
    }
    
    // 遍历右子树，找到则返回
    Node* right_result = depth_first_preorder_s(root->right,x);
    if (right_result != nullptr) {
        return right_result;
    }
    
    // 没找到返回nullptr
    return nullptr;
}

修正后的中序遍历函数 #

template<typename T> inline typename BST<T>::Node* BST<T>::depth_first_inorder_s(Node* root, T x) {
    //若根节点为空
    if (!root) return nullptr;
    
    // 遍历左子树，找到则返回
    Node* left_result = depth_first_inorder_s(root->left,x);
    if (left_result != nullptr) {
        return left_result;
    }
    
    // 检查当前节点
    if (root->data == x) {
        return root;
    }
    
    // 遍历右子树，找到则返回
    Node* right_result = depth_first_inorder_s(root->right,x);
    if (right_result != nullptr) {
        return right_result;
    }
    
    // 没找到返回nullptr
    return nullptr;
}

这样修改后，不管哪种遍历顺序，只要在子树中找到目标节点，就会立刻把结果沿着调用栈返回，不会做无用的遍历，也不会出现返回错误节点的情况啦。

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