LeetCode 热题 100_二叉树的最近公共祖先（48_236_中等_C++）(二叉树；深度优先搜索)

题目描述：

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

输入输出样例：

示例 1：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

示例 2：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

示例 3：
输入：root = [1,2], p = 1, q = 2
输出：1

提示：
树中节点数目在范围 [2, 10⁵] 内。
-10⁹ <= Node.val <= 10⁹
所有 Node.val 互不相同 。
p != q
p 和 q 均存在于给定的二叉树中。

题解：

解题思路：

思路一（深度优先搜索）：

1、在解决此问题时我们首先应该讨论一下p，q在二叉树中的各个分布情况。假设一个结点为root为当前遍历的结点。
递归出口：
            ① root结点为null则返回（递归出口）(返回null)
            ② 当前结点为p,返回p（第一次发现p，且未找到q）(返回当前结点，因当前结点可能为祖先)
（为什么直接返回呢，因为我们可以通过遍历除p的子孙节点外的其他结点来判断q的位置：若其他结点中存在q，则p不是q的祖先。若其他结点不存在q，则q是p的子孙，p为公共祖先结点）
            ③ 当前结点为q,返回q（第一次发现q，且未找到p）(返回当前结点，因当前结点可能为祖先)
（为什么直接返回呢，因为我们可以通过遍历除q的子孙节点外的其他结点来判断p的位置：若其他结点存在p则，q不是p的祖先。若其他结点不存在p，则p是q的子孙，q为公共祖先结点）

递归体： 按深度优先遍历递归的寻找左右子树。

判断当前节点的左右子树（左右子树遍历完后）：
             ① 当前结点左右子树都没有查找到p或q。（返回null）
             ② 当前结点左子树找到一个结点(p或q),右子树找到一个结点(p或q)。(返回当前结点，当前结点为公共祖先)
             ③当前结点左子树找到一个结点(p或q)，右子树没找到。(返回左子树找到的结点)
             ④ 当前结点右子树找到一个结点(p或q)，左子树没找到。(返回右子树找到的结点)

2、复杂度分析：
① 时间复杂度：O(n)，n代表二叉树中结点的个数，最坏的情况会遍历整颗二叉树。
② 空间复杂度：O(n)，采用的是深度遍历搜索，所以需要用到函数栈，最坏情况下为O(n)。

代码实现

代码实现（思路一（深度优先搜索））：

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    //遍历到nullptr或者p、 q则返回
    if (root==nullptr||root==p||root==q) return root;
    
    //递归的进行查找
    TreeNode *left=lowestCommonAncestor(root->left,p,q);
    TreeNode *right=lowestCommonAncestor(root->right,p,q);
    
    //如果当前结点的左右子树都没查找到q或p，则返回nullptr
    if(left==nullptr&&right==nullptr) return nullptr;
    //查找到p、q的公共祖先则返回该结点
    if (left!=nullptr&&right!=nullptr) return root;
    //p或q存在左子树则返回左子树对应的结点
    if (left!=nullptr) return left;
    //p或q存在右子树则返回右子树对应的结点
    return right; 
}

以思路一为例进行调试

#include<iostream>
#include <vector>
#include <queue>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

//通过数组创建二叉树，-1代表nullptr;
TreeNode *createTree(vector<int> nums){
    if (nums.empty())
    {
        return nullptr;
    }
    queue<TreeNode *> q;
    TreeNode *root=new TreeNode(nums[0]);
    q.push(root);
    int i=1;
    while (i<nums.size())
    {
        TreeNode *node=q.front();
        q.pop();
        if (i<nums.size()&&nums[i]!=-1)
        {
            node->left=new TreeNode(nums[i]);
            q.push(node->left);
        }
        ++i;
        if (i<nums.size()&&nums[i]!=-1)
        {
            node->right=new TreeNode(nums[i]);
            q.push(node->right);
        }
        ++i;
    }
    return root;
}

//用于检查二叉树是否创建正确
void inorderTraversal(TreeNode *root){
    if (root==nullptr)
    {
        return ;
    }
    inorderTraversal(root->left);
    cout<<root->val<<" ";
    inorderTraversal(root->right);
}

//二叉树的最近公共祖先
class Solution
{
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        //遍历到nullptr或者p、 q则返回
        if (root==nullptr||root==p||root==q) return root;
        
        //递归的进行查找
        TreeNode *left=lowestCommonAncestor(root->left,p,q);
        TreeNode *right=lowestCommonAncestor(root->right,p,q);
        
	    //如果当前结点的左右子树都没查找到q或p，则返回nullptr
	    if(left==nullptr&&right==nullptr) return nullptr;
        //查找到p、q的公共祖先则返回该结点
        if (left!=nullptr&&right!=nullptr) return root;
        //p或q存在左子树则返回左子树对应的结点
        if (left!=nullptr) return left;
        //p或q存在右子树则返回右子树对应的结点
        return right; 
    }
};


int main(int argc, char const *argv[])
{
    //-1代表null
    vector<int> nums={3,5,1,6,2,0,8,-1,-1,7,4};
    //通过nums数组创建二叉树
    TreeNode *root=createTree(nums);

    //用于检查二叉树是否创建正确
    //inorderTraversal(root);

    //计算root->left和root->right的最近公共祖先
    Solution s;
    TreeNode *ans = s.lowestCommonAncestor(root,root->left,root->right);
    cout<<ans->val;
    return 0;
}

LeetCode 热题 100_二叉树的最近公共祖先（48_236)原题链接
欢迎大家和我沟通交流(✿◠‿◠)