第一时间想的实际上是倍增，就是对于每个节点，记录它的 \(2^k\) 级祖先，查询 LCA 的时候让它们先跳到同一深度，接着再逐步向父节点移动
但是这样需要去预处理，并且这里是直接给出了函数和传进来的数据结构，所以换个角度考虑
怎么转换角度呢，如果考虑怎么去实现，那实际上还是一开始提到的思路
但是想到树的结构本身就是子结构或者同构问题，适合动态规划或者分治
这里我们要编写的函数的作用是在根为 root 的树中，找 p, q 的 LCA
考虑 p, q 可能的分布
- 一个在左子树，一个在右子树
- 两个都在左子树
- 两个都在右子树
对于第一种情况，显然 LCA 就是 root
对于第 2 、3 种情况，我们的结果等价于在根为 root 的左/右儿子 中，找 p, q 的 LCA
接着我们思考如何去刻画这一个关系，因为我们需要一个统一的策略，去处理 1，2，3
延续上面提到的思想，尝试把这个任务丢给左子树，右子树，也就是
TreeNode *l = lowestCommonAncestor(root->left, p, q);TreeNode *r = lowestCommonAncestor(root->right, p, q);
如果是情况 2 ，那么 r 会是 nullptr ，返回 l ，反之亦然
如果是情况 1， 那么 l 和 r 都会是 nullptr，这时候返回 root
现在剩下递归边界情况
如果 root 已经是 nullptr ，自然返回 root；特殊一点的，如果 root 恰好是 p, q ，那么显然 LCA 是 root
/*** 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 || root == p || root == q) {return root;}TreeNode *l = lowestCommonAncestor(root->left, p, q);TreeNode *r = lowestCommonAncestor(root->right, p, q);if(l == nullptr) {return r;}if(r == nullptr) {return l;}return root;}
};
另外在翻看别人的代码时发现 nullptr 或者说是否为空的判断可以写的更简单一些，也就是类似于判断是否为 0 的形式
class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if (!root || 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;}if (left) {return left;}return right;}