一、题目
二、思路
求两个节点的最近公共祖先的题目我们做过，但是这题是二叉搜索树BST，并且本题中所有节点的数值都是不同的，所以可以根据BST的数值特点进行判断，即左子树的所有节点都比当前节点小，右子树的所有节点都比当前节点数值大。
若 root 是 p,q 的 最近公共祖先 ，则只可能为以下情况之一：
p 和 q 在 root 的子树中，且分列 root 的 异侧（即分别在左、右子树中）；
p = root，且 q 在 root 的左或右子树中；
q = root，且 p 在 root 的左或右子树中；
方法一：迭代法
循环搜索： 当节点 root 为空时跳出；
当 p, q 都在 root 的 右子树 中，则遍历至 root.right ；
否则，当 p, q 都在 root 的 左子树 中，则遍历至 root.left ；
否则，说明找到了 最近公共祖先 ，跳出。
返回值： 最近公共祖先 root 。
/** * 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) { while(root){ if(root->val < p->val && root->val < q->val){ root = root->right; }else if(root->val > p->val && root->val > q->val){ root = root->left; }else{ break; } } return root; } };
时间复杂度：O(N)，其中N为二叉树节点数，每while训练一轮就“处理”完一层，BST树的最小高度为logN，最大高度为N（退化为链表）。
空间复杂度：O(1)，使用常数大小的额外空间。
方法二：递归
其实就是把迭代法中的while循环去掉，还是分三种情况，但是在前两种情况里递归。
/** * 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){ return lowestCommonAncestor(root->right, p, q); }else if(p->val < root->val && q->val < root->val){ return lowestCommonAncestor(root->left, p, q); } return root; } };
