当前位置：首页 > news >正文

剑指Offer68-II.二叉树的最近公共祖先 C++

news 2025/7/12 23:23:49

1、题目描述

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
示例 1:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
示例 2:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。

2、VS2019上运行

使用存储父节点的方法

#include <iostream>
#include <unordered_map>
using namespace std;// 二叉树节点的定义
struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};class Solution {
public:unordered_map<int, TreeNode*> fa; // 父节点哈希表unordered_map<int, bool> vis; // 访问标记哈希表// 进行深度优先搜索，为每个节点分配父节点void dfs(TreeNode* root) {if (root->left != nullptr) {fa[root->left->val] = root;dfs(root->left);}if (root->right != nullptr) {fa[root->right->val] = root;dfs(root->right);}}// 在二叉树中找到两个节点的最近公共祖先TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {fa[root->val] = nullptr;dfs(root);//遍历树填充父节点哈希表while (p != nullptr) {vis[p->val] = true;// 将节点p标记为已访问p = fa[p->val];// 将p移动到其父节点}while (q != nullptr) {if (vis[q->val]) return q;//如果节点q已被标记为已访问，说明q是最近公共祖先，直接返回qq = fa[q->val];//将q移动到其父节点}return nullptr;}
};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->left->right->left = new TreeNode(7);root->left->right->right = new TreeNode(4);root->right->left = new TreeNode(0);root->right->right = new TreeNode(8);// 定义两个节点，用于查找它们的最近公共祖先TreeNode* p = root->left;TreeNode* q = root->right;// 创建解决方案类的实例Solution obj;// 寻找最近公共祖先TreeNode* lca = obj.lowestCommonAncestor(root, p, q);// 打印最近公共祖先的值if (lca != nullptr) {cout << "最近公共祖先: " << lca->val << endl;}else {cout << "未找到最近公共祖先。" << endl;}// TODO: 删除动态分配的树节点，以避免内存泄漏return 0;
}