脚本宝典收集整理的这篇文章主要介绍了[基础二叉树算法]求两个节点的最近公共祖先，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
先定义数据结构
typedef struct {
int value;
Node *left;
Node *right;
} Node;算法：
void findCommonRoot(Node *root, Node *n1, Node *n2) {
if (!root) {
return NULL;
}
// 当前节点为其中一个，直接return。
if (root == n1 || root == n2) {
return root;
}
Node *left = findCommonRoot(root->left, n1, n2);
Node *right = findCommonRoot(root->right, n1, n2);
// 当前节点下，左右都能找到，则当前节点就是最近共同父节点。
if (left && right) {
return root;
}
// 如果只找到了一个，返回对应的那个。
if (left || right) {
return left ? : right;
}
return NULL;
}举个栗子：
比如下图，
1
2 3
4 5 6 7
8 9
- 找4和9.
当函数递归到root=2的时候，
left进去4开始找，找到return 4.
right进去5开始找，最终找到9，return 9。此时root=2的时候，left和right都有值。return 2.
- 找4和7
当函数递归到root=1的时候，
left进去，2开始找，最终return 4
right进去，3开始找，最终return 7
此时root=1的时候，left和right都有值，return1.
- 找4和8，
当函数递归到root=4的时候，
left进去，直接return 4.
right进去，return null。此时由于只找到了4，return 4.
再往回return的时候，root = 2时，left = 4.return 4.
往回 root = 1 时，left = 4，
right = null， 故最终return 4.
以上是脚本宝典为你收集整理的[基础二叉树算法]求两个节点的最近公共祖先全部内容，希望文章能够帮你解决[基础二叉树算法]求两个节点的最近公共祖先所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。