第54章 二叉树的搜索算法
搜索知识点 /

第54章 二叉树的搜索算法

本讲对应 GESP C++ 六级知识块 · 搜索算法（DFS、BFS、二叉树搜索）

考核目标：掌握深度优先搜索（DFS，含先/中/后序）与广度优先搜索（BFS，层次遍历）的思想；能根据实际问题（目标在浅层还是深层、是否求路径）选择合适的搜索算法。

核心知识点：

  • DFS：用栈/递归深入，适合遍历全部节点、求路径
  • BFS：用队列按层扩展，适合优先找浅层目标
  • 二叉树上的按值搜索、按条件搜索与路径搜索（回溯）

同一棵树的 DFS 与 BFS 访问顺序

二叉树的搜索算法是指在二叉树中查找满足特定条件的节点（如查找指定值、符合条件的路径等）的方法。由于二叉树属于非线性结构，搜索策略和数组、链表存在明显区别，需要结合遍历方式设计查找逻辑。

54.1 二叉树搜索的基本概念

54.1.1 搜索目标

  1. 查找包含特定值的节点
  2. 查找叶子节点、最大值节点、最小值节点等满足特定属性的节点
  3. 查找从根节点到目标节点的完整路径
  4. 查找所有根到叶子、节点值之和等于目标的路径

54.1.2 搜索策略分类

  1. 深度优先搜索（DFS）：包含前序、中序、后序遍历，适合需要深入遍历深层节点的场景
  2. 广度优先搜索（BFS，层次遍历）：按层级依次访问，适合优先查找浅层目标节点

54.2 按值搜索算法

54.2.1 深度优先（递归）实现

二叉树节点基础定义：

#include <iostream>
using namespace std;
struct TreeNode{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode (int x): val(x), left (NULL), right (NULL) {}
};

前序搜索：根 → 左 → 右

TreeNode* preorderSearch (TreeNode *root, int target) {
    if (root == NULL){
        return NULL;
    }
    if (root->val == target){
        return root;
    }
    TreeNode *leftResult = preorderSearch (root->left, target);
    if (leftResult!= NULL){
        return leftResult;
    }
    return preorderSearch (root->right, target);
}

中序搜索：左 → 根 → 右

TreeNode* inorderSearch (TreeNode *root, int target) {
    if (root == NULL){
        return NULL;
    }
    TreeNode *leftResult = inorderSearch (root->left, target);
    if (leftResult != NULL){
        return leftResult;
    }
    if (root->val == target){
        return root;
    }
    return inorderSearch (root->right, target);
}

后序搜索：左 → 右 → 根

TreeNode* postorderSearch (TreeNode *root, int target) {
    if (root == NULL){
        return NULL;
    }
    TreeNode *leftResult = postorderSearch (root->left, target);
    if (leftResult != NULL){
        return leftResult;
    }
    TreeNode *rightResult = postorderSearch (root->right, target);
    if (rightResult != NULL){
        return rightResult;
    }
    if (root->val == target){
        return root;
    }
    return NULL;
}

说明：三种深度优先搜索仅访问节点的时机不同；普通无序二叉树三者效率一致；二叉排序树可利用有序性优化中序搜索。

54.2.2 广度优先（层次）实现

#include <queue>
using namespace std;
TreeNode* levelorderSearch (TreeNode *root, int target) {
    if (root == NULL){
        return NULL;
    }
    queue<TreeNode*> q;
    q.push (root);
    while (!q.empty()){
        TreeNode *node = q.front();
        q.pop();
        if (node->val == target){
            return node;
        }
        if (node->left != NULL){
            q.push (node->left);
        }
        if (node->right != NULL){
            q.push (node->right);
        }
    }
    return NULL;
}

优势：目标节点处于浅层时，无需遍历深层分支，查找速度更快。

54.3 按条件搜索算法

54.3.1 查找所有叶子节点

#include <vector>
using namespace std;
void findLeaves (TreeNode *root, vector<TreeNode*>& leaves){
    if (root == NULL){
        return;
    }
    if (root->left == NULL && root->right == NULL) {
        leaves.push_back (root);
        return;
    }
    findLeaves (root->left, leaves);
    findLeaves (root->right, leaves);
}

54.3.2 查找最大值节点（递归）

TreeNode* findMax (TreeNode *root) {
    if (root == NULL){
        return NULL;
    }
    TreeNode *leftMax = findMax(root->left);
    TreeNode *rightMax = findMax(root->right);
    TreeNode *maxNode = root;
    if (leftMax != NULL && leftMax->val > maxNode->val)
        maxNode = leftMax;
    if (rightMax != NULL && rightMax->val > maxNode->val)
        maxNode = rightMax;
    return maxNode;
}

54.3.3 查找最小值节点（层次遍历）

TreeNode* findMin (TreeNode *root) {
    if (root == NULL){
        return NULL;
    }
    TreeNode *minNode = root;
    queue<TreeNode*> q;
    q.push (root);
    while (!q.empty()){
        TreeNode *node = q.front();
        q.pop();
        if (node->val < minNode->val){
            minNode = node;
        }
        if(node->left!= NULL){
            q.push (node->left);
        }
        if (node->right != NULL) {
            q.push (node->right);
        }
    }
    return minNode;
}

54.3.4 查找指定深度k的所有节点

void findNodesAtDepth (TreeNode *root, int k, vector<TreeNode*>& result) {
    if (root == NULL || k<1){
        return;
    }
    queue<TreeNode*> q;
    q.push (root);
    int currentDepth=1;
    while (!q.empty()){
        int levelSize = q.size();
        if (currentDepth == k){
            for (int i =0; i<levelSize; i++) {
                result.push_back(q.front());
                q.pop();
            }
            return;
        }
        for (int i=0;i<levelSize; i++) {
            TreeNode *node = q.front();
            q.pop();
            if (node->left!= NULL){
                q.push (node->left);
            }
            if (node->right != NULL){
                q.push (node->right);
            }
        }
        currentDepth++;
    }
}

54.4 路径搜索算法

54.4.1 回溯查找根到目标节点路径

bool findPathToTarget(TreeNode *root, int target, vector<TreeNode*> path) {
    if(root == NULL){
        return false;
    }
    path.push_back (root);
    if (root->val == target) {
        return true;
    }
    bool leftFound = findPathToTarget (root->left, target, path);
    if(leftFound){
        return true;
    }
    bool rightFound = findPathToTarget (root->right, target);
    if(rightFound){
        return true;
    }
    path.pop_back();
    return false;
}

54.4.2 查找根到叶子、和为目标的全部路径

void findPathsWithSum(TreeNode *root, int target, int currentSum, vector<int>& currentPath, vector<vector<int>>& result){
    if (root == NULL){
        return;
    }
    currentSum += root->val;
    currentPath.push_back (root->val);
    if (root->left == NULL && root->right == NULL && currentSum == target)
    {
        result.push_back (currentPath);
    } else{
        findPathsWithSum (root->left, target, currentSum, currentPath, result);
        findPathsWithSum (root->right, target, currentSum, currentPath, result);
    }
    currentPath.pop_back();
}

//对外调用接口
vector<vector<int>> getPathsWithSum(TreeNode *root, int target){
    vector<vector<int>> result;
    vector<int> currentPath;
    findPathsWithSum(root, target, 0, currentPath, result);
    return result;
}

54.5 二叉排序树高效搜索

54.5.1 BST非递归查找实现

TreeNode* bstSearch (TreeNode *root, int target) {
    TreeNode *current = root;
    while (current != NULL) {
        if (current->val == target){
            return current;
        } else if (target < current->val){
            current=current->left;
        }else{
            current=current->right;
        }
    }
    return NULL;
}

54.5.2 优势分析

普通无序二叉树最坏需要遍历全部节点，时间复杂度O(n)O(n)； 平衡二叉排序树每次排除一半分支，时间复杂度O(log⁡n)O(\log n)。

54.6 搜索算法的优化策略

剪枝优化示例（路径求和提前终止无效分支）

void findPathsWithSumPruned (TreeNode *root, int target, int currentSum, vector<int>& path, vector<vector<int>>& result) {
    if(root== NULL || currentSum>target){
        return;
    }
    //后续遍历逻辑与原版保持一致
}
  1. 剪枝：路径求和场景，当前累加值已超过目标则直接终止该分支递归
  2. 缓存：频繁查询最大/最小值时，缓存结果避免重复全树遍历
  3. 遍历选择
    • 浅层目标优先BFS层次遍历
    • 需要遍历全树使用DFS
    • BST必须使用专用有序查找逻辑

54.7 注意事项

  1. 空树处理：所有遍历、查找函数开头必须判断root == NULL，防止空指针异常
  2. 回溯正确性：路径记录类递归，递归返回前必须pop弹出当前节点，避免路径冗余
  3. 重复值处理：树存在重复节点值时，区分「找到第一个匹配节点」「收集所有匹配节点」两种需求
  4. 复杂度总结
    • 普通二叉树全量搜索：O(n)O(n)
    • 平衡二叉排序单次查找：O(log⁡n)O(\log n)
    • 退化斜BST最坏查找：O(n)O(n)

练习题

  1. 在一棵很"宽"但很"浅"的二叉树中查找一个位于第 2 层的节点，从效率角度通常优先选用（ ） A. 深度优先搜索（DFS） B. 广度优先搜索（BFS） C. 后序遍历 D. 都可以，没有差别

    答案与解析

    答案：B

    解析：BFS 按层扩展，一旦在浅层找到目标就立即返回，无需深入更深的子树；DFS 会沿一条分支一直走到叶子才回溯，目标在浅层时反而可能遍历更多无关深层节点。因此浅层目标优先 BFS。

  2. 在一个无序的普通二叉树中，按值搜索一个节点，最坏情况下需要访问的节点数约为（ ） A. O(log⁡n)O(\log n) B. O(1)O(1) C. O(n)O(n) D. O(nlog⁡n)O(n \log n)

    答案与解析

    答案：C

    解析：无序二叉树没有可利用的有序性，最坏情况下目标节点在最后才被访问，或根本不存在，需要遍历全部 nn 个节点，复杂度 O(n)O(n)。只有平衡二叉排序树（BST）才能达到 O(log⁡n)O(\log n)。

  3. 使用 DFS 搜索"根到叶子、路径上节点值之和等于目标值"的所有路径时，回溯过程必须（ ） A. 到达叶子后立即结束程序 B. 在递归返回前把当前节点从路径中弹出（pop） C. 不需要任何额外操作 D. 把整棵树复制到数组里再判断

    答案与解析

    答案：B

    解析：路径记录类 DFS 用 path 向量记录从根到当前的路径。进入节点时压入，递归返回（无论是否找到）前必须弹出该节点，否则路径会残留其他分支的节点，导致结果错误。这正是回溯法的关键。

  4. 对于一棵平衡二叉排序树（BST），单次按值查找的时间复杂度是（ ） A. O(n)O(n) B. O(log⁡n)O(\log n) C. O(n2)O(n^2) D. O(1)O(1)

    答案与解析

    答案：B

    解析：平衡 BST 每次比较都能排除约一半分支，树高约为 log⁡n\log n，因此查找复杂度 O(log⁡n)O(\log n)。若退化为斜树（如插入有序序列且未平衡），才会退化到 O(n)O(n)。

SShowball OI知识手册