【LeetCode热题100】【二叉树】二叉树的最近公共祖先

题目链接：236. 二叉树的最近公共祖先 - 力扣（LeetCode）

二叉树皆可递归，可以递归查找两个节点的所在地，如果两个节点一个在root的左子树一个在右子树，说明root就是公共祖先，并且因为是递归，root就是最近的，如果不是，往左右子树递归的时候返回来空的，那说明最近公共祖先在非空的一侧，如果root就是两个节点之一，那么就直接返回

class Solution {
public:TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {if (root == nullptr || root == p || root == q)return root;TreeNode *left = lowestCommonAncestor(root->left, p, q);TreeNode *right = lowestCommonAncestor(root->right, p, q);if (left == nullptr)return right;if (right == nullptr)return left;return root;}
};