题目来源

解题方法

思路：只要根节点的值在p, q之间，即为答案了

/*** 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((p->val - root->val)*(q->val - root->val) <= 0)return root;if(p->val > root->val)return lowestCommonAncestor(root->right, p, q);if(p->val < root->val)return lowestCommonAncestor(root->left, p, q);return NULL;}
};

如果把二叉搜索树改成二叉树呢？

关键点：找到一个节点，p，q分别在其两侧即可，若p，q其中一个本身就是最近的公共祖先节点，那只需要找到他，不用再继续往下找了，因为另一侧肯定返回NULL，当前返回的就是答案

/*** 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 == NULL || root == p || root == q)return root;// 进入左右节点，看看能不能找到TreeNode* left = lowestCommonAncestor(root->left, p, q);TreeNode* right = lowestCommonAncestor(root->right, p, q);if(left == NULL)return right;if(right == NULL)return left;// 都找到了，说明root就是答案return root;}
};