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

寻找二叉树中两个节点的最低公共祖先

news 来源：原创 2024/9/20 9:42:53

在二叉树中寻找两个节点的最低公共祖先（Lowest Common Ancestor，LCA）是一个经典的问题。在这个问题中，最低公共祖先是指在二叉树中，两个节点的公共祖先中离它们最近的那个节点。

问题定义

给定一棵二叉树的根节点和两个节点 p 和 q，要求找到这两个节点的最低公共祖先。

方法一：递归法

一种常见的解决方案是使用递归。基本思想是通过递归遍历二叉树，从根节点开始，寻找 p 和 q 的位置。如果在某个节点下找到了 p 和 q，那么这个节点就是它们的最低公共祖先。

代码示例（C++）

#include <iostream>
using namespace std;// 定义二叉树节点
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);// 如果 p 和 q 分别在当前节点的左右子树中，则当前节点就是 LCAif (left != nullptr && right != nullptr) {return root;}// 否则，返回非空的那个子树return left != nullptr ? left : right;
}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);TreeNode* p = root->left;         // Node 5TreeNode* q = root->left->right->right;  // Node 4TreeNode* lca = lowestCommonAncestor(root, p, q);if (lca != nullptr) {cout << "Lowest Common Ancestor: " << lca->val << endl;} else {cout << "Lowest Common Ancestor not found" << endl;}return 0;
}

代码解析

递归基准条件：
- 如果当前节点是 nullptr，或者当前节点是 p 或 q，那么这个节点可能是 LCA（或者当前子树中没有公共祖先），因此直接返回当前节点。
递归搜索左右子树：
- 对当前节点的左右子树分别进行递归搜索，找到 p 和 q 的位置。
确定 LCA：
- 如果 p 和 q 分别位于左右子树中，则当前节点即为最低公共祖先。
- 如果只在某一侧找到了 p 或 q，则返回找到的那个节点。
返回结果：
- 如果递归最终找到某个节点是公共祖先，则返回该节点；否则返回 nullptr。