二叉树两点最短距离 C++
时间: 2023-11-14 08:06:16 浏览: 36
以下是使用C++编写的二叉树两点最短距离的代码示例:
```cpp
#include <iostream>
#include <queue>
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// 寻找最低公共祖先节点
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == nullptr || root == p || root == q) {
return root;
}
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
if (left && right) {
return root;
} else if (left) {
return left;
} else {
return right;
}
}
// 计算节点到最低公共祖先节点的距离
int distanceToLCA(TreeNode* node, TreeNode* target) {
if (node == nullptr) {
return INT_MAX;
}
if (node == target) {
return 0;
}
return 1 + std::min(distanceToLCA(node->left, target), distanceToLCA(node->right, target));
}
// 计算最短距离
int shortestDistance(TreeNode* root, TreeNode* p, TreeNode* q) {
TreeNode* lca = lowestCommonAncestor(root, p, q);
int distance_p = distanceToLCA(lca, p);
int distance_q = distanceToLCA(lca, q);
return distance_p + distance_q;
}
int main() {
// 创建二叉树
TreeNode* root = new TreeNode(3);
root->left = new TreeNode(5);
root->right = new TreeNode(1);
root->left->left = new TreeNode(6);
root->left->right = new TreeNode(2);
root->right->left = new TreeNode(0);
root->right->right = new TreeNode(8);
root->left->right->left = new TreeNode(7);
root->left->right->right = new TreeNode(4);
// 寻找节点5和节点4的最短距离
int distance = shortestDistance(root, root->left, root->left->right->right);
std::cout << distance << std::endl; // 输出2,即节点5和节点4之间的最短距离
return 0;
}
```
请注意,此示例代码中使用了C++标准库的queue和iostream头文件,并假设了树中的节点值不重复。在实际应用中,你可能需要根据具体情况进行调整。