[二叉树]面试题 04.08. 首个共同祖先(medium)

首个共同祖先(medium)"/>

[二叉树]面试题 04.08. 首个共同祖先(medium)

题目：

题解：

• 递归三部曲，写好递归出口，递归式和处理递归结果便可得解。
• 首个公共祖先有三种情况：
• 1）p、q为以 root 为根节点的左右子树中，则 root 为祖先
• 2）p、q在以 root 为节点的左子树中，则 root->left 为祖先（即在右子树中找不到p、q节点）
• 3）p、q在以 root 为节点的右子树中，则 root->right为祖先（即在左子树中找不到p、q节点）

代码如下：

class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {//1、递归出口：根节点为空，或者找到p或q节点了if(!root||root==p||root==q)return root;//2、递归式：从根节点的左右子树寻找p、q的节点TreeNode *left=lowestCommonAncestor(root->left,p,q);TreeNode *right=lowestCommonAncestor(root->right,p,q);//3、判断其祖先的位置if(left&&right)return root;//在以root为根节点的左右子树中找到p、q节点了，则root为祖先if(left&&!right)return left;//在以root为根节点的右子树没找到p、q节点，则其左子树根节点为祖先return right;在以root为根节点的左子树没找到p、q节点，则其右子树根节点为祖先}
};