---

1）

DFS 前序遍历二叉树，记录根到当前节点的路径。

每当进入一个节点，计算根到该节点的路径和。

如果路径和等于 k，则输出当前路径（从 path[0] 到 path[pathLen-1]）。

递归遍历左子树和右子树。回溯时恢复 pathLen。

2）

void FindValidPaths(BiTree T, int k, int *path, int pathLen) {
    if (T == NULL) return;

    // 将当前节点加入路径
    path[pathLen] = T->val;
    pathLen++;

    // 检查从根到当前节点的路径和是否等于 k
    int sum = 0;
    for (int i = 0; i < pathLen; i++) {
        sum += path[i];
    }
    if (sum == k) {
        printPath(path, pathLen);
    }

    // 递归遍历左子树和右子树
    FindValidPaths(T->lchild, k, path, pathLen);
    FindValidPaths(T->rchild, k, path, pathLen);

    // 回溯：pathLen 在递归返回后自动恢复（因为传值），所以不需要显式删除
    // 实际上 pathLen 是值传递，递归返回后回到原来的值
}

3）

时间复杂度：每个节点访问一次，在访问每个节点时，计算从根到当前节点的路径和需要 O(路径长度)，路径长度最大为树高 h。所以总复杂度为 O(n × h)，在平衡树中 h = log n，最坏链状树 h = n，所以最坏 O(n²)，平均 O(n log n)。

空间复杂度：递归栈空间 O(h)，路径数组空间 O(h)，所以总空间复杂度 O(h)。

---