无需最低公共祖先（LCA）或根节点路径，能否计算普通树中两节点的距离？

嘿，这个问题问得挺有意思的！先直接给你结论：完全可以不用显式查找LCA或者根节点路径，就能计算普通树中两个节点的距离，核心思路是把“追踪节点深度”和“判断两个目标节点的位置关系”合并到一次遍历中。

具体思路 #

我们可以通过一次递归遍历整棵树，对每个节点做两件事：

• 检查当前节点是否是目标节点p或q
• 从所有子节点那里获取它们各自子树中到p和q的距离

当遍历到某个节点时，会出现几种情况：

1. 当前节点本身是p或q：先标记它到自身的距离为0，然后看子节点里有没有另一个目标节点——如果有，直接返回两者距离之和；如果没有，就把“当前是目标节点”的信息向上传递。
2. 当前节点的子树中同时找到了p和q的距离：比如一个子树返回了到p的距离，另一个返回了到q的距离，那这两个距离之和就是p和q之间的总距离。
3. 只有一个子树返回了其中一个目标节点的距离：把这个距离+1（因为当前节点到子节点的距离是1）继续向上传递。
4. 子树里都没找到目标节点：返回无效标记（比如-1）。

示例代码实现 #

这里用C++写一个具体的实现，思路和上面一致：

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

struct TreeNode {
    int val;
    vector<TreeNode*> children;
    TreeNode(int x) : val(x) {}
};

// 返回值：pair<到p的距离, 到q的距离>，-1表示未找到
pair<int, int> calculateDistanceHelper(TreeNode* root, TreeNode* p, TreeNode* q, int& result) {
    if (!root) return {-1, -1};

    pair<int, int> current = {-1, -1};
    if (root == p) current.first = 0;
    if (root == q) current.second = 0;

    for (auto child : root->children) {
        auto childDist = calculateDistanceHelper(child, p, q, result);
        // 如果子节点已经找到结果，直接返回
        if (result != -1) return {-1, -1};

        // 合并子节点的距离信息
        if (childDist.first != -1) {
            if (current.first == -1) {
                current.first = childDist.first + 1;
            }
        }
        if (childDist.second != -1) {
            if (current.second == -1) {
                current.second = childDist.second + 1;
            }
        }

        // 检查是否同时找到了p和q的距离
        if (current.first != -1 && current.second != -1) {
            result = current.first + current.second;
            return {-1, -1};
        }
    }

    return current;
}

int getDistance(TreeNode* root, TreeNode* p, TreeNode* q) {
    int result = -1;
    calculateDistanceHelper(root, p, q, result);
    return result;
}

对比你的LCA代码 #

你贴的LCA代码是通过统计子树中找到目标节点的数量来定位LCA，而这个方法相当于把“找LCA”和“计算距离”合并了——当我们在某个节点同时拿到了两个目标节点的距离时，这个节点其实就是LCA，直接计算距离即可，不用单独把LCA找出来再分别算距离。

这种方法的优势是只需要一次遍历，时间复杂度是O(n)（n是树的节点数），和显式找LCA再算距离的时间复杂度一样，但避免了额外的步骤，代码也更紧凑。

备注：内容来源于stack exchange，提问作者Jagdeep Kaur