题目描述
blablabla
样例
blablabla
算法1
( 递归) $O(n)$
我自己感觉呢，有好多种情况， 讲不清楚，自己勉强来整理整理，希望大家一起指正、讨论。
- root 的值等于 p 的值或者 q 的值
这种时候直接返回 root 这个 node 就好了。 - root 的左边、右边都返回了一个node
这种时候也是直接返回 root 就好了。 - root 的右边或者左边返回了一个node， 另一边的返回值是空的。
这种时候返回右边或者左边那个不是空的的node。 - 如果左边、右边的返回值都是空的
这就只好返回空的值了。 - （这个感觉应该放在最前面）如果连 root 都是空的话
也要返回空指针，这个应该是这一条路走到底的情况了。
我感觉呢，还是理解得不是很透彻，希望大神们一起加油，互相帮助，共同促进！
时间、空间复杂度分析：都是o(n)?
C++ 代码
##### (递归) $O(n)$
#### C++ 代码
'''
/**
* 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) {
return nullptr;
}
if (root->val == p->val || root->val == q->val) {
return root;
}
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
if (left && right) {
return root;
} else if (left) {
return left;
} else if (right) {
return right;
}
return nullptr;
}
};
'''
时间复杂度分析： 我自己感觉时间复杂度和空间复杂度都是o(n), 大家觉得呢？
很清晰，感谢
赞！！！感觉你的思路 和 y总方法一 差不多
如果p,q没有公共祖先，返回的节点岂不是 有问题
简单明了
我的理解是这样的，应该会比较好懂：
原则是，如果找到目标Node，就返回这个Node，如果不是目标Node（没找到）就返回Null。
然后递归：
先判断该节点是不是Null，如果是，则该节点肯定不是目标，故应该返回Null；
然后看该节点是不是就是目标，如果是，则把该节点Node返回（相当于返回true）；
然后对该节点的左右子节点进行递归，并将返回值记录（left 和 right）
因为我们的原则是，如果找到就返回节点值，找不到就返回Null，因此如果left 和 right都不是null，说明该节点左右都有目标值，也就是说该节点就是我们要找的公共节点，故返回该节点即可。
如果有一个节点返回Null，另一个不是Null，则说明返回Null的那个子树里没有目标值，而返回的不是Null的子树里有目标值，因此需要返回有目标值的那个节点（表示该节点的左子树或右子树有目标值）
如果两个子节点都返回Null，说明该节点以下都没有目标值，此路不通，所以要返回null，表示没有目标值。
时间和空间复杂度应该都是O(N)，这个思路感觉跟Leet Code官解的Recursion的思路是一样的，但是实现更简单一点
牛逼
求问空间复杂度和时间复杂度怎么具体分析？
很优秀的递归
很赞的解法