1. 题目
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
2. 示例
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
3. 分析
方法一：
1.对于二叉树，从根开始搜索，查找两个子节点的位置
（1）都在左子树，递归到左子树去找
（2）都在右子树，递归到右子树去找
（3）一个节点在左子树，一个节点在右子树，那么根就是最近公共祖先
2.找节点时，用指针去找，不能用值去找，因为有可能二叉树中存在值相等的节点
由于方法一在极端情况下复杂度为O(N^2)
因此可以使用下面的方法将时间复杂度优化为O(N)
方法二 借助栈存节点路径，假如要找6和4的最近公共祖先：
（1）从最左开始，找6：
3不是6，有可能是6的路径上的节点，入栈，
5不是6，有可能是6的路径上的节点，入栈
6，找到了，入栈
（2）从最左开始，找4：
3不是4，有可能是4的路径上的节点，入栈
5不是4，有可能是4的路径上的节点，入栈
6不是4，有可能是4的路径上的节点，入栈
6是叶子节点，这条路径上不可能有4，6出栈
2不是4，有可能是4的路径上的节点，入栈
7不是4，有可能是4的路径上的节点，入栈
7是叶子节点，这条路径上不可能有4，7出栈
4找到了，入栈
（3）确定长栈和短栈，让长栈先走差距步，然后长短栈一起走，找相同的栈顶元素
4. 代码实现
方法一：
1. /** 2. * Definition for a binary tree node. 3. * struct TreeNode { 4. * int val; 5. * TreeNode *left; 6. * TreeNode *right; 7. * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8. * }; 9. */ 10. class Solution { 11. public: 12. bool Find(TreeNode* root,TreeNode* x) 13. { 14. if(root == nullptr) 15. { 16. return false; 17. } 18. 19. if(x == root) 20. { 21. return true; 22. } 23. 24. return Find(root->left,x)||Find(root->right,x); 25. } 26. 27. TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { 28. 29. if(p == root || q == root) 30. { 31. return root; 32. } 33. 34. //题目已经说明p和q一定在树中 35. bool ispInLeft,ispInRight,isqInLeft,isqInRight; 36. 37. //如果p不在左子树，那么p一定在右子树 38. //不需要在左右子树中都查找p，只需要在左子树中查找p 39. ispInLeft = Find(root->left,p); 40. printf("ispInLeft = %d\n",ispInLeft); 41. ispInRight = !ispInLeft; 42. 43. //如果q不在左子树，那么q一定在右子树 44. //不需要在左右子树中都查找q，只需要在左子树中查找q 45. isqInLeft = Find(root->left,q); 46. printf("isqInLeft = %d\n",isqInLeft); 47. isqInRight = !isqInLeft; 48. 49. if(ispInLeft && isqInLeft)//p和q都在左子树中，就去左子树中找 50. { 51. 52. return lowestCommonAncestor(root->left,p,q); 53. 54. } 55. else if(ispInRight && isqInRight)//p和q都在右子树中，就去右子树中找 56. { 57. return lowestCommonAncestor(root->right,p,q); 58. } 59. else//一个在左子树，一个在右子树，根就是公共祖先 60. { 61. return root; 62. } 63. } 64. };
方法二：
1. class Solution { 2. public: 3. //找节点所在路径 4. bool FindPath(TreeNode* root,TreeNode* x,stack<TreeNode*>& path) 5. { 6. if(root == nullptr) 7. { 8. return false; 9. } 10. 11. path.push(root); 12. 13. if(root == x) 14. { 15. return true; 16. } 17. 18. if(FindPath(root->left,x,path)) 19. { 20. return true; 21. } 22. 23. if(FindPath(root->right,x,path)) 24. { 25. return true; 26. } 27. 28. //左右子树都没有x,那么说明root不是路径中的节点，pop 29. path.pop(); 30. return false; 31. } 32. TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) 33. { 34. stack<TreeNode*> pPath,qPath; 35. FindPath(root,p,pPath); 36. FindPath(root,q,qPath); 37. 38. //确定长栈和短栈 39. stack<TreeNode*>* longPath = &pPath; 40. stack<TreeNode*>* shortPath = &qPath; 41. 42. if(pPath.size() < qPath.size()) 43. { 44. swap(longPath,shortPath); 45. } 46. 47. //让长的先走差距步 48. while(longPath->size() > shortPath->size()) 49. { 50. longPath->pop(); 51. } 52. 53. //同时走，找交点 54. while(longPath->top() != shortPath->top()) 55. { 56. longPath->pop(); 57. shortPath->pop(); 58. } 59. 60. return longPath->top(); 61. } 62. };
