面试题 04.08. 首个共同祖先[递归，深度优先遍历]

vlambda
2022-03-09

面试题 04.08. 首个共同祖先[递归，深度优先遍历]

题目描述

面试题 04.08. 首个共同祖先

原题传送：https://leetcode-cn.com/problems/first-common-ancestor-lcci/

面试题 04.08. 首个共同祖先[递归，深度优先遍历]

考察知识

深度优先遍历，递归

解题思路

寻找距离两个节点最近的祖先，最近可以理解为从下向上寻找，最先找到的节点即为所求。

因此考虑使用递归遍历，进行深度优先遍历，因为是最近的公共祖先，因此可以设置判断的条件为(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; }};