LeetCode 热题 100_二叉树的最近公共祖先（49_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，则返回nullptrif(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，则返回nullptrif(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代表nullvector<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_二叉树的最近公共祖先（49_236)原题链接
欢迎大家和我沟通交流(✿◠‿◠)