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

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;
}

最近公共祖先: 3

3、解题思路

（官方）

• 1、从根节点开始遍历整棵二叉树，用哈希表记录每个节点的父节点指针。
• 2、从 p 节点开始不断往它的祖先移动，并用数据结构记录已经访问过的祖先节点。
• 3、同样，我们再从 q 节点开始不断往它的祖先移动，如果有祖先已经被访问过，即意味着这是 p 和 q 的深度最深的公共祖先，即 LCA 节点

4、二叉树和二叉搜索树的区别

• 在二叉搜索树中，对于每个节点，其左子树中的所有节点的值都小于该节点的值，而右子树中的所有节点的值都大于该节点的值。对于普通的二叉树，没有节点值的有序性要求，节点的排列相对自由。节点可以按照任意方式组织，没有特定的约束条件。