题目描述

设计并实现一个算法，找出二叉树中某两个节点的第一个共同祖先。不得将其他的节点存储在另外的数据结构中。注意：这不一定是二叉搜索树。

例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]

    3/ \5   1/ \ / \
6  2 0  8/ \7   4

示例 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。因为根据定义最近公共祖先节点可以为节点本身。

说明:
所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉树中。

解题思路与代码

对于写递归函数而言，要分别搞清楚三件事，分别是：

1. 递归函数的返回类型与形参是什么？
2. 递归函数该如何结束/返回？
3. 单层递归的逻辑是什么？

递归查找公共祖先节点

这道题我认为是一道十分注重细节的递归题。为什么这么说呢，这是因为有很多条件，你少写了或者位置写错了，那么这一道题，就很有可能误入歧途，写错了。

那请大家跟着我的思路走一遍，我是这么思考这道题的。
这道题，我简答的思考了一下，我就打算在原函数上进行递归，因为我发现我并不需要传递多余参数，且返回值是TreeNode*类型，刚刚好，所以就在原函数上进行递归了。

然后就可以开始去思考递归的终止条件是什么了。那么首先，如果root节点若为空，那肯定就得返回null。其次，如果root节点等于p或q节点，那就直接返回root。在不然，就去判断root->left,与root->right。

这里着重要去注意： 我们要用 一个新的节点去递归root->left、root->right，而不是直接让 root->left去递归它本身。用代码表示就是要这样写：

TreeNode* left = lowestCommonAncestor(root->left,p,q);
TreeNode* right = lowestCommonAncestor(root->right,p,q);

而不是这样写：

root->left = lowestCommonAncestor(root->left,p,q);
root->right = lowestCommonAncestor(root->right,p,q);

这里是这个代码的第一个易错点

紧接着，我们要开始另一部分的结束判断了。这里还有一个易错点，这里的代码要这样写：

if(left && right) return root;
else if(left && !right) return left;
else if(!left && right) return right;return nullptr;

而不是这样写：

if(left && !right) return left
else if(right && !left) return right;
else return rootreturn nullptr;

我们要记住，这里其实是一个有四种情况的，一种是left为空，right不为空，一种是left不为空，right为空，一种是都不为空，一种是都为空。

少写一种判断，就都写错了。

这道题就这两个最容易错的点。如果都写对了，那这道题就对了。

/*** 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 == nullptr) return nullptr;if(root == p || root == q) return root;TreeNode* left = lowestCommonAncestor(root->left,p,q);TreeNode* right = lowestCommonAncestor(root->right,p,q);if(left && right) return root;else if(left && !right) return left;else if(!left && right) return right;return nullptr;}
};

复杂度分析：

时间复杂度：O(N)，其中 N 为二叉树中的节点数。对于每个节点最多会访问一次，所以时间复杂度为 O(N)。

空间复杂度：O(h)，其中 h 表示二叉树的高度。

总结

这道题不算太难的题，但也有些难度。在我的理解上，这道题有两个易错点。一不留神就会写错，一定得多多注意！