c++求解二叉树两个节点间距离
时间: 2024-12-24 16:38:57 浏览: 36
在 C++ 中,求解二叉树中两个节点间的最短路径(即距离),可以使用递归或层次遍历的方法。这里我们假设二叉树是以指针结构表示的,并且每个节点都有指向左右子节点和父节点的引用。
一种常见的方法是使用深度优先搜索 (DFS) 或广度优先搜索 (BFS) 结合哈希映射存储已访问过的节点,避免重复计算。以下是基于递归的 DFS 解法:
```cpp
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
int distanceInBinaryTree(TreeNode* root, TreeNode* target1, TreeNode* target2) {
unordered_set<TreeNode*> visited; // 用于存储已经访问过的节点
return dfs(root, target1, target2, visited);
}
int dfs(TreeNode* node, TreeNode* target1, TreeNode* target2, unordered_set<TreeNode*>& visited) {
if (!node || node == target1 || node == target2) {
return node == target1 ? 0 : INT_MAX; // 如果到达目标节点返回距离,未到达则返回最大值
}
visited.insert(node); // 标记当前节点已访问
int distToTarget1 = dfs(node->left, target1, target2, visited);
int distToTarget2 = dfs(node->right, target1, target2, visited);
return min(distToTarget1, distToTarget2) + 1; // 返回到左、右子树中较近的目标的距离加1(因为每一步都是向下)
}
```
在这个函数里,`distanceInBinaryTree` 是主入口,它调用了 `dfs` 函数并初始化了访问集合。`dfs` 通过递归查找从根节点到目标1和目标2的最短路径,同时跟踪已访问节点以防止回溯。
阅读全文
相关推荐

















