题目描述
给出一个二叉树，输入两个树节点，求它们的最低公共祖先。
一个树节点的祖先节点包括它本身。
注意：
- 输入的二叉树不为空；
- 输入的两个节点一定不为空，且是二叉树中的节点；
数据范围
树中节点数量 [0,500]。
样例
二叉树[8, 12, 2, null, null, 6, 4, null, null, null, null]如下图所示： 8 / \ 12 2 / \ 6 4 1. 如果输入的树节点为2和12，则输出的最低公共祖先为树节点8。 2. 如果输入的树节点为2和6，则输出的最低公共祖先为树节点2。
方法一：二叉树+递归 O(n)
这道题我们递归的去查找，分别去递归每个结点的左右子树，我们拿题目样例进行举例。
假如我们要寻找 12 和 4 的最低公共祖先，则会先从根结点 8 向下进行递归查找，首先递归左子树，发现 12 就已经是目标结点，故直接返回该结点。
而根结点 8 的右结点不是目标结点，所以会继续递归左右结点，而 2 左子树中没有目标结点，最终会返回 NULL 。但其右子树中有目标结点 4 ，故会返回 4 ，然后结点 2 又会向其父结点返回查找到的结点 4 。
至此，根结点 8 左右子树查找结果都不为空，所以结点 8 就是目标结点 12 和 4 的最低公共祖先。
我们再看个例子，假设要寻找 2 和 4 的最低公共祖先。同样从根结点 8 出发向下递归，发现左子树中没有目标结点，最终返回 NULL 。而右子树中遍历到第一个结点 2 就会直接返回，因为 2 已经是目标结点，所以根结点 8 会得到答案 2 ，这个 2 就是 2 和 4 的最低公共祖先。
/** * 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) { //如果没有遍历到p或q，最终会遍历到空结点，直接返回NULL if (!root) return NULL; //如果遍历到p或者q，则直接返回 if (p == root || q == root) return root; //获得左右子树的遍历情况 auto left = lowestCommonAncestor(root->left, p, q); auto right = lowestCommonAncestor(root->right, p, q); //如果两个子树的遍历结果都不为空，则说明当前结点就是最低公共结点 if (left && right) return root; //如果右子树遍历结果为空，则说明右子树中没有目标结点或者答案在左子树中 if (left && !right) return left; //反之，左子树为空，则说明左子树中没有目标节点或者答案在右孩子中 return right; } };
欢迎大家在评论区交流~
