题目描述：
给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的val值 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。
数据范围：树上节点数满足1≤n≤10^5 , 节点值val满足区间 [0,n)
要求：时间复杂度 O(n)
注：本题保证二叉树中每个节点的val值均不相同。
如当输入{3,5,1,6,2,0,8,#,#,7,4},5,1时，二叉树{3,5,1,6,2,0,8,#,#,7,4}如下图所示：
所以节点值为5和节点值为1的节点的最近公共祖先节点的节点值为3，所以对应的输出为3。
节点本身可以视为自己的祖先
示例：
输入：
{3,5,1,6,2,0,8,#,#,7,4},5,1
返回值：
3
解题思路：
本题考察数据结构树的使用，寻找最近公共祖先，用LCA算法解决。
1. 如果两个节点均在左子树内，则LCA(root,o1,o2)=LCA(root->left,o1,o2)；若其中一个节点正好是左子树根节点，则左子树根节点就是它俩的最近公共祖先。
2. 如果两个节点均在右子树内，则LCA(root,o1,o2)=LCA(root->right,o1,o2)；若其中一个节点正好是右子树根节点，则右子树根节点就是它俩的最近公共祖先。
3. 如果一个在左子树，一个在右子树，则当前的根节点就是最近公共祖先。
测试代码：
/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ class Solution { public: // LCA算法：寻找最近公共祖先 TreeNode* LCA(TreeNode* root,int r1,int r2){ // 节点为空 if(!root) return NULL; // 是否寻找到目标值 if(root->val == r1 || root->val == r2) return root; // 递归 TreeNode* left=LCA(root->left,r1,r2); TreeNode* right=LCA(root->right,r1,r2); // 若左边有，右边没有，则目标在左边；若右边有，左边有，则目标在右边 if(!left) return right; if(!right) return left; // 若左边和右边都有节点，则当前根为公共祖先 return root; } int lowestCommonAncestor(TreeNode* root, int o1, int o2) { TreeNode* result=LCA(root,o1,o2); return result->val; } };
