NC102 最近公共祖先 C++ 题解
若 root 是 p, q的 最近公共祖先 ，则只可能为以下情况之一：
p 和 q 在 root 的子树中，且分列 root 的 异侧（即分别在左、右子树中）；
p = root，且 q 在 root 的左或右子树中；
q = root，且 p 在 root 的左或右子树中；
p 和 q 在 root 的子树中，且分列 root 的 异侧（即分别在左、右子树中）；
p = root，且 q 在 root 的左或右子树中；
q = root，且 p 在 root 的左或右子树中；
递归查找即可，代码如下：
/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
class Solution {
public:
/**
*
* @param root TreeNode类
* @param o1 int整型
* @param o2 int整型
* @return int整型
*/
TreeNode *find(TreeNode* root, int o1, int o2) {
if(root == NULL || root->val == o1 || root->val == o2) return root;
TreeNode *l = find(root->left, o1, o2);
TreeNode *r = find(root->right, o1, o2);
if(!l) return r;
if(!r) return l;
return root;
}
int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
// write code here
TreeNode *ret = find(root, o1, o2);
return ret->val;
}
};
查看19道真题和解析