首个共同祖先(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节点,则其右子树根节点为祖先}
};
更多推荐
[二叉树]面试题 04.08. 首个共同祖先(medium)
发布评论