面试题 04.08. 首个共同祖先[递归，深度优先遍历]
题目描述
面试题 04.08. 首个共同祖先
原题传送：https://leetcode-cn.com/problems/first-common-ancestor-lcci/
考察知识
深度优先遍历，递归
解题思路
寻找距离两个节点最近的祖先，最近可以理解为从下向上寻找，最先找到的节点即为所求。
因此考虑使用递归遍历，进行深度优先遍历，因为是最近的公共祖先，因此可以设置判断的条件为(left && right) || ((root->val == p->val || root->val == q->val) && (left || right))
(left && right)表示左右子树分别都有要查询的目标节点
((root->val == p->val || root->val == q->val) && (left || right)表示本节点就是要寻找的节点之一，另外只要无论左子树还是右子树之中只要包含另一个节点即可。（之所以可以合并讨论是因为题中明确给出没有重复的节点）
具体解题思路见代码：
解题代码
// 面试题 04.08. 首个共同祖先struct TreeNode{int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}};class Solution{public:TreeNode *res; // 存储输出的结果bool dfs(TreeNode *root, TreeNode *p, TreeNode *q){if (root == NULL){// 到达了叶子节点return false;}bool left = dfs(root->left, p, q);bool right = dfs(root->right, p, q);if ((left && right) || ((root->val == p->val || root->val == q->val) && (left || right))){// 满足条件 记录结果res = root;}// 从下向上传递return left || right || (root->val == p->val || root->val == q->val);}TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q){// 使用深度优先遍历寻找两个节点最近的共同祖先dfs(root, p, q);return res;}};
写在最后
欢迎大家转发给朋友一起打卡学习哦！
任何问题欢迎后台私信阿哲！
点个在看你最好看