什么是树上搜索？

树上搜索 是指在树形数据结构上进行搜索、遍历或查找特定节点的算法。树是一种重要的非线性数据结构，广泛应用于文件系统、DOM 树、算法竞赛等场景。

常见的树上搜索包括：

• 树的遍历：前序、中序、后序、层序
• 节点查找：查找特定节点或特定条件的节点
• 路径查找：找到两个节点之间的路径
• 最近公共祖先（LCA）：找到两个节点的最近公共祖先

树的表示方法

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// 树节点结构
struct TreeNode {
    int val;
    vector<TreeNode*> children;
    TreeNode* left;   // 用于二叉树
    TreeNode* right;  // 用于二叉树
    
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 邻接表表示（用于一般树）
vector<vector<int>> tree_adj;

// 二叉树的建立（基于数组）
TreeNode* build_binary_tree(const vector<int>& arr) {
    if (arr.empty() || arr[0] == -1) return nullptr;
    
    vector<TreeNode*> nodes;
    for (int x : arr) {
        nodes.push_back(x == -1 ? nullptr : new TreeNode(x));
    }
    
    int n = arr.size();
    for (int i = 0; i < n; i++) {
        if (nodes[i]) {
            int left_idx = 2 * i + 1;
            int right_idx = 2 * i + 2;
            if (left_idx < n) nodes[i]->left = nodes[left_idx];
            if (right_idx < n) nodes[i]->right = nodes[right_idx];
        }
    }
    
    return nodes[0];
}

二叉树的搜索遍历

// 前序遍历（根-左-右）
void preorder(TreeNode* root) {
    if (!root) return;
    cout << root->val << " ";
    preorder(root->left);
    preorder(root->right);
}

// 中序遍历（左-根-右）
void inorder(TreeNode* root) {
    if (!root) return;
    inorder(root->left);
    cout << root->val << " ";
    inorder(root->right);
}

// 后序遍历（左-右-根）
void postorder(TreeNode* root) {
    if (!root) return;
    postorder(root->left);
    postorder(root->right);
    cout << root->val << " ";
}

// 层序遍历（广度优先）
void levelorder(TreeNode* root) {
    if (!root) return;
    queue<TreeNode*> q;
    q.push(root);
    
    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        cout << node->val << " ";
        
        if (node->left) q.push(node->left);
        if (node->right) q.push(node->right);
    }
}

节点查找与路径

// 在二叉树中查找值为 target 的节点
TreeNode* find_node(TreeNode* root, int target) {
    if (!root) return nullptr;
    if (root->val == target) return root;
    
    TreeNode* left = find_node(root->left, target);
    if (left) return left;
    
    return find_node(root->right, target);
}

// 查找从根到目标节点的路径
bool find_path(TreeNode* root, int target, vector<int>& path) {
    if (!root) return false;
    
    path.push_back(root->val);
    
    if (root->val == target) return true;
    
    if (find_path(root->left, target, path)) return true;
    if (find_path(root->right, target, path)) return true;
    
    path.pop_back();  // 回溯
    return false;
}

// 查找两个节点的最近公共祖先（LCA）
TreeNode* find_lca(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (!root || root == p || root == q) return root;
    
    TreeNode* left = find_lca(root->left, p, q);
    TreeNode* right = find_lca(root->right, p, q);
    
    if (left && right) return root;
    return left ? left : right;
}

一般树的搜索（邻接表）

vector<int> tree_find_path(int n, const vector<vector<int>>& adj, int start, int target) {
    vector<int> parent(n, -1);
    queue<int> q;
    q.push(start);
    parent[start] = start;
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        
        if (u == target) break;
        
        for (int v : adj[u]) {
            if (parent[v] == -1) {
                parent[v] = u;
                q.push(v);
            }
        }
    }
    
    // 还原路径
    vector<int> path;
    if (parent[target] == -1) return path;  // 无路径
    
    for (int v = target; v != start; v = parent[v]) {
        path.push_back(v);
    }
    path.push_back(start);
    reverse(path.begin(), path.end());
    
    return path;
}

完全实现示例

int main() {
    // 构建二叉树:     1
    //              /   \
    //             2     3
    //            / \   \
    //           4   5   6
    
    vector<int> arr = {1, 2, 3, 4, 5, -1, 6};
    TreeNode* root = build_binary_tree(arr);
    
    cout << "前序遍历: ";
    preorder(root);   // 输出: 1 2 4 5 3 6
    cout << endl;
    
    cout << "中序遍历: ";
    inorder(root);    // 输出: 4 2 5 1 3 6
    cout << endl;
    
    cout << "后序遍历: ";
    postorder(root);  // 输出: 4 5 2 6 3 1
    cout << endl;
    
    cout << "层序遍历: ";
    levelorder(root); // 输出: 1 2 3 4 5 6
    cout << endl;
    
    // 查找路径
    vector<int> path;
    find_path(root, 5, path);
    cout << "从根到节点5的路径: ";
    for (int v : path) cout << v << " ";
    cout << endl;
    
    return 0;
}

复杂度分析

操作	时间复杂度	空间复杂度
前/中/后序遍历	O(n)	O(h)，h为树高
层序遍历	O(n)	O(w)，w为最大宽度
节点查找	O(n)	O(h)
LCA	O(n)	O(h)

总结

树上搜索是算法竞赛和工程实践中的基础技能。掌握各种遍历方式、理解递归与回溯的思想，对于解决更复杂的树形问题（如二叉搜索树、平衡树、线段树等）至关重要。