一、树的遍历问题

问题描述

给定一棵含有 n 个节点的无向树，节点编号从 0 到 n-1。再给定一个节点 x 作为根节点，请分别输出以 x 为根节点的深度优先搜索（DFS）遍历序列和广度优先搜索（BFS）遍历序列。

输入格式

第一行输入整数 n（1 ≤ n ≤ 200000），表示树的节点数量。

接下来 n-1 行，第 i 行（i 从 1 到 n-1）输入一个整数 a_i（0 ≤ a_i ≤ i），表示节点 i 与节点 a_i 之间存在一条边。

最后一行输入整数 x（0 ≤ x < n），表示根节点编号。

输出格式

输出两行，每行 n 个整数。第一行为 DFS 遍历序列，第二行为 BFS 遍历序列。

重要要求：对于拥有多个子节点的节点，遍历时应按照子节点编号从大到小的顺序进行。

解题思路

本题的核心在于实现两种经典的树遍历算法，同时满足特定的子节点访问顺序要求。

深度优先搜索（DFS） 采用递归方式实现，从根节点出发，沿着树的深度方向尽可能深入地访问节点。当到达叶子节点后，回溯到上一个节点继续访问其他分支。由于题目要求按编号递减顺序遍历子节点，因此需要首先对每个节点的邻接表进行降序排序。

广度优先搜索（BFS） 使用队列数据结构实现，按层次顺序访问节点。从根节点开始，先访问所有距离为 1 的节点，再访问距离为 2 的节点，依此类推。同样需要对子节点进行降序处理以满足题目要求。

参考实现

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN = 200005;

vector<int> edges[MAXN];
bool visited[MAXN];
int queueArray[MAXN];

// 按编号升序排列以便后续反向遍历
bool compareDescending(int a, int b) {
    return a > b;
}

// 添加无向边
void addEdge(int u, int v) {
    edges[u].push_back(v);
    edges[v].push_back(u);
}

// 深度优先搜索遍历
void depthFirstSearch(int root) {
    cout << root << ' ';
    visited[root] = true;
    
    // 由于已按降序排列，直接遍历即可
    for (int i = 0; i < edges[root].size(); i++) {
        int nextNode = edges[root][i];
        if (!visited[nextNode]) {
            visited[nextNode] = true;
            depthFirstSearch(nextNode);
        }
    }
}

// 广度优先搜索遍历
void breadthFirstSearch(int root) {
    int front = 0, rear = 0;
    queueArray[rear++] = root;
    visited[root] = true;
    
    while (front < rear) {
        int current = queueArray[front++];
        cout << current << ' ';
        
        for (int i = 0; i < edges[current].size(); i++) {
            int nextNode = edges[current][i];
            if (!visited[nextNode]) {
                visited[nextNode] = true;
                queueArray[rear++] = nextNode;
            }
        }
    }
}

int main() {
    int n, root;
    cin >> n;
    
    for (int i = 1; i <= n - 1; i++) {
        int parent;
        cin >> parent;
        addEdge(parent, i);
    }
    
    cin >> root;
    
    // 对所有节点的邻接表进行降序排序
    for (int i = 0; i < n; i++) {
        sort(edges[i].begin(), edges[i].end(), compareDescending);
    }
    
    memset(visited, 0, sizeof(visited));
    depthFirstSearch(root);
    cout << endl;
    
    memset(visited, 0, sizeof(visited));
    breadthFirstSearch(root);
    cout << endl;
    
    return 0;
}

---

二、树的直径与中心

问题描述

给定一棵含有 n 个节点的无向树，所有边的长度均为 1。请计算该树的直径长度，并找出树的中心节点。

树的中心定义为：到树上所有节点的最大距离最小的节点。一棵树可能有一个或两个中心节点。

输入格式

第一行输入整数 n（1 ≤ n ≤ 200000），表示树的节点数量。

接下来 n-1 行，第 i 行（i 从 1 到 n-1）输入一个整数 a_i（0 ≤ a_i < i），表示节点 i 与节点 a_i 之间存在一条边。

输出格式

输出两行。第一行输出一个整数，表示树的直径长度。第二行按编号升序输出所有中心节点的编号。

解题思路

树的直径 是指树上任意两点之间最短路径的最大值。计算树的直径采用两次广度优先搜索的方法：

第一次 BFS：从任意节点（通常选择节点 0）出发，找出距离该节点最远的节点，这个节点一定是直径的一端。

第二次 BFS：从第一次找到的端点出发，再次进行 BFS，这次得到的最大距离就是树的直径，同时可以记录每个节点的父节点信息用于回溯路径。

树的中心 是到树上所有节点的最远距离最小的节点。直径长度为偶数时，中心唯一；直径长度为奇数时，中心为直径中点相邻的两个节点。

参考实现

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN = 200005;

struct NodeInfo {
    int distance;
    int parent;
};

vector<int> edges[MAXN];
bool visited[MAXN];
int bfsQueue[MAXN];
NodeInfo nodeData[MAXN];

void addEdge(int u, int v) {
    edges[u].push_back(v);
    edges[v].push_back(u);
}

// 广度优先搜索，返回距离起点最远的节点
int breadthFirstSearch(int start) {
    int front = 0, rear = 0;
    bfsQueue[rear++] = start;
    visited[start] = true;
    nodeData[start].distance = 0;
    nodeData[start].parent = -1;
    
    int farthestNode = start;
    
    while (front < rear) {
        int current = bfsQueue[front++];
        
        for (int i = 0; i < edges[current].size(); i++) {
            int neighbor = edges[current][i];
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                nodeData[neighbor].distance = nodeData[current].distance + 1;
                nodeData[neighbor].parent = current;
                bfsQueue[rear++] = neighbor;
                
                if (nodeData[neighbor].distance > nodeData[farthestNode].distance) {
                    farthestNode = neighbor;
                }
            }
        }
    }
    
    return farthestNode;
}

int main() {
    int n;
    cin >> n;
    
    for (int i = 1; i <= n - 1; i++) {
        int parent;
        cin >> parent;
        addEdge(parent, i);
    }
    
    // 按降序排列邻接表，保证遍历顺序
    for (int i = 0; i < n; i++) {
        sort(edges[i].begin(), edges[i].end(), greater<int>());
    }
    
    // 第一次BFS找到直径的一个端点
    memset(visited, 0, sizeof(visited));
    int endpoint = breadthFirstSearch(0);
    
    // 第二次BFS计算直径并获取路径信息
    memset(visited, 0, sizeof(visited));
    memset(nodeData, 0, sizeof(nodeData));
    int otherEnd = breadthFirstSearch(endpoint);
    
    int diameter = nodeData[otherEnd].distance;
    cout << diameter << endl;
    
    // 根据直径长度确定中心节点
    if (diameter % 2 == 0) {
        // 偶数直径，中心唯一
        int current = otherEnd;
        while (nodeData[current].distance != diameter / 2) {
            current = nodeData[current].parent;
        }
        cout << current << endl;
    } else {
        // 奇数直径，有两个中心
        int center1 = -1, center2 = -1;
        int current = otherEnd;
        
        while (current != -1) {
            if (nodeData[current].distance == (diameter + 1) / 2) {
                center1 = current;
            }
            if (nodeData[current].distance == (diameter - 1) / 2) {
                center2 = current;
                break;
            }
            current = nodeData[current].parent;
        }
        
        if (center1 > center2) swap(center1, center2);
        cout << center1 << ' ' << center2 << endl;
    }
    
    return 0;
}

算法复杂度分析

对于 n 个节点的树，两道题的时间复杂度均为 O(n)，因为每个节点和每条边都只被访问常数次。空间复杂度同样为 O(n)，主要用于存储邻接表、队列和标记数组。