二叉树的最近公共祖先

拼搏现实的明天。 2023-10-06 08:04 76阅读 0赞

## 二叉树的最近公共祖先 ##

#### 问题： ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70 1]

#### 思路： ####

###### 分治递归： ######

在二叉树中寻找节点p,q：要么p或q为根节点，在这种情况下，根节点即为最近公共祖先。要么p,q 分布在左子树或右子树中。若p,q分别分布在左右子树，根节点即为最近公共祖先，若p,q都处于左子树或右子树中，则处理对象变为根的左子树或右子树，对左子树或右子树递归求解。

递归函数的功能为寻找节点p,q的最近公共祖先，若根节点即为p或q，直接返回根节点，否则对左子树和右子树分别调用递归函数。若对左子树调用递归函数的返回值为空指针，表明p,q均在右子树中，返回对右子树调用递归函数的返回值（处理对象变为右子树，因为p,q均在右子树中）。若对右子树调用递归函数的返回值为空指针，表明p,q均在左子树中，返回对左子树调用递归函数的返回值（处理对象变为左子树，因为p,q均在左子树中）。若对左右子树调用递归函数的返回值均不为空，表明p,q分别处于左右子树中，此时根节点即为最近公共祖先，返回根节点。

#### 代码： ####

/**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
        
    public:
        TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        
            if( root==NULL || root==p || root==q )
                return root;
            TreeNode* left=lowestCommonAncestor( root->left,p,q );
            TreeNode* right=lowestCommonAncestor( root->right,p,q );
            if( left==NULL  )
                return  right;
            if( right==NULL )
                return  left;
            return root;
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200504165203184.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200504165235839.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw,size_16,color_FFFFFF,t_70