EC07-使用递归方法找出从根节点到叶子节点的最长路径¶

代码实现¶

C
// 函数 allpath：使用递归方法找出从根节点到叶子节点的最长路径
// 参数说明：
// p - 当前访问的二叉树节点
// st[] - 存储当前路径的栈数组
// top - 指向栈顶位置的指针
// max - 指向最长路径长度的指针
// res[] - 存储最长路径结果的数组
void allpath(BiTree p, char st[], int *top, int *max, char res[]) {
    // 递归终止条件：如果当前节点不为空
    if (p != NULL) {
        // 将当前节点数据压入路径栈
        st[++(*top)] = p->data;

        // 判断是否为叶子节点
        if (!p->lchild && !p->rchild) {
            // 如果是叶子节点，检查当前路径长度是否为最长
            if (*top > *max) {
                // 更新最长路径长度
                *max = *top;
                // 将当前路径复制到结果数组中
                for (int i = 0; i <= *top; i++) {
                    res[i] = st[i];
                }
            }
        }

        // 递归处理左子树
        allpath(p->lchild, st, top, max, res);

        // 递归处理右子树
        allpath(p->rchild, st, top, max, res);

        // 回溯：当前节点处理完毕，从路径栈中弹出
        (*top)--;
    }
}

代码逻辑解析¶

1. 算法核心思想¶

使用深度优先搜索（DFS）遍历所有从根到叶子的路径
采用回溯法记录当前路径
动态维护并更新最长路径

2. 关键数据结构¶

st[]：路径栈，存储当前正在探索的路径
top：栈顶指针，指示当前路径的长度
res[]：结果数组，存储找到的最长路径
max：记录最长路径的长度

3. 算法流程¶

路径记录：将当前节点加入路径栈
叶子节点判断：检查是否到达叶子节点
最长路径更新：如果是叶子节点且路径更长，则更新结果
递归探索：继续探索左右子树
回溯处理：当前节点处理完毕，从路径中移除

4. 回溯机制¶

C
1 2	`// 递归调用前：st[++(top)] = p->data; // 加入路径 // 递归调用后：(top)--; // 从路径移除`

时间复杂度分析¶

1. 遍历节点数¶

需要访问二叉树中的每个节点
设二叉树有 n 个节点

2. 每次访问的处理¶

叶子节点：需要进行路径复制操作，最坏情况下复制 h 个元素（h 为树高）
非叶子节点：O(1) 的基本操作

3. 路径复制开销¶

最坏情况下，每个叶子节点都需要复制一次路径
设叶子节点数为 L，平均路径长度为 h
路径复制总开销：O(L × h)

4. 总体时间复杂度¶

访问所有节点：O(n)
路径复制：O(L × h) ≤ O(n)
总时间复杂度：O(n)

空间复杂度分析¶

1. 额外数组空间¶

st[]：路径栈，最大长度为树的高度 h
res[]：结果数组，最大长度为树的高度 h
数组空间：O(h)

2. 递归调用栈¶

递归深度等于树的高度 h
调用栈空间：O(h)

3. 总体空间复杂度¶

O(h)，其中 h 是树的高度 - 最好情况（完全二叉树）：O(log n) - 最坏情况（退化为链表）：O(n)

较难理解部分的说明¶

1. 回溯机制的重要性¶

C
// 示例说明回溯过程
/*
树结构：
    A
   / \
  B   C
 /   / \
D   E   F

探索路径过程：
1. A → B → D (叶子)：路径 [A,B,D]，长度3
2. 回溯 B：路径 [A,B] → B处理完毕
3. 回溯 A：路径 [A] → 探索右子树
4. A → C → E (叶子)：路径 [A,C,E]，长度3
5. 回溯 C：路径 [A,C] → 探索右子树
6. A → C → F (叶子)：路径 [A,C,F]，长度3
*/

2. 指针参数的作用¶

C
// top 使用指针的原因
void demonstrate_pointer_necessity() {
    // 错误示例：值传递
    void wrong_func(int top) {
        top++; // 只修改局部副本，不影响调用者
    }

    // 正确示例：指针传递
    void correct_func(int *top) {
        (*top)++; // 修改原始变量
    }
}

3. 图解说明¶

假设二叉树结构如下：

Text Only
1 2 3 4 5 6 7	`A / \ B C / / \ D E F / G`

路径探索过程：

Text Only

路径栈变化：
[A]           // 访问A
[A,B]         // 访问B
[A,B,D]       // 访问D (叶子，路径长度3)
[A,B]         // 回溯D
[A]           // 回溯B
[A,C]         // 访问C
[A,C,E]       // 访问E (叶子，路径长度3)
[A,C]         // 回溯E
[A,C,F]       // 访问F (叶子，路径长度3)
[A,C]         // 回溯F
[A]           // 回溯C

最长路径：A→C→F (长度3)

延伸知识点¶

1. 改进版本 - 返回所有最长路径¶

C
// 找出所有最长路径
void findAllLongestPaths(BiTree p, char st[], int *top, int *max, 
                        char paths[][MAX_PATH], int *path_count) {
    if (p != NULL) {
        st[++(*top)] = p->data;

        if (!p->lchild && !p->rchild) {
            if (*top > *max) {
                // 发现更长路径，清空之前的记录
                *max = *top;
                *path_count = 1;
                for (int i = 0; i <= *top; i++) {
                    paths[0][i] = st[i];
                }
            } else if (*top == *max) {
                // 发现同样长度的路径
                for (int i = 0; i <= *top; i++) {
                    paths[*path_count][i] = st[i];
                }
                (*path_count)++;
            }
        }

        findAllLongestPaths(p->lchild, st, top, max, paths, path_count);
        findAllLongestPaths(p->rchild, st, top, max, paths, path_count);

        (*top)--;
    }
}

2. 非递归版本 - 使用栈实现¶

C
void findLongestPathIterative(BiTree root, char res[]) {
    if (root == NULL) return;

    Stack* node_stack = createStack();     // 节点栈
    Stack* path_stack = createStack();     // 路径栈
    int max_length = 0;

    push(node_stack, root);
    push_char(path_stack, root->data);

    while (!isEmpty(node_stack)) {
        BiTree node = pop(node_stack);
        char data = pop_char(path_stack);

        // 如果是叶子节点
        if (!node->lchild && !node->rchild) {
            if (path_stack->size > max_length) {
                max_length = path_stack->size;
                // 复制当前路径到结果数组
                copyStackToArray(path_stack, res);
            }
        }

        // 添加子节点到栈中
        if (node->rchild) {
            push(node_stack, node->rchild);
            push_char(path_stack, node->rchild->data);
        }
        if (node->lchild) {
            push(node_stack, node->lchild);
            push_char(path_stack, node->lchild->data);
        }
    }
}

3. 返回路径长度的版本¶

C
int getLongestPathLength(BiTree p) {
    if (p == NULL) return 0;
    if (!p->lchild && !p->rchild) return 1;

    int left_length = getLongestPathLength(p->lchild);
    int right_length = getLongestPathLength(p->rchild);

    return 1 + max(left_length, right_length);
}

4. 相关算法问题¶

最短根到叶路径：¶

C
void findShortestPath(BiTree p, char st[], int *top, int *min, char res[]) {
    if (p != NULL) {
        st[++(*top)] = p->data;

        if (!p->lchild && !p->rchild) {
            if (*top < *min) {  // 注意这里是 < 而不是 >
                *min = *top;
                for (int i = 0; i <= *top; i++) {
                    res[i] = st[i];
                }
            }
        }

        findShortestPath(p->lchild, st, top, min, res);
        findShortestPath(p->rchild, st, top, min, res);

        (*top)--;
    }
}

所有根到叶路径：¶

C
void printAllPaths(BiTree p, char path[], int path_len) {
    if (p == NULL) return;

    path[path_len] = p->data;
    path_len++;

    if (!p->lchild && !p->rchild) {
        // 打印路径
        for (int i = 0; i < path_len; i++) {
            printf("%c ", path[i]);
        }
        printf("\n");
    } else {
        printAllPaths(p->lchild, path, path_len);
        printAllPaths(p->rchild, path, path_len);
    }
}

5. 实际应用场景¶

文件系统：找出目录树中最深的文件路径
网络路由：找出最长的网络路径
决策树：分析决策过程的最长路径
游戏AI：计算游戏树的最深搜索路径

这个算法体现了回溯法和路径搜索的经典思想，是树算法中的重要问题。通过维护当前路径和最长路径，能够高效地解决路径相关问题。