题目：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
代码：
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
TreeNode res = root;
while (true){
if (p.val < res.val && q.val < res.val) {
//p和q都小于res，证明p和q都在res的左子树
res = res.left;
} else if (p.val > res.val && q.val > res.val) {
//p和q都大于res，证明p和q都在res的右子树
res = res.right;
}else{
//上述条件都不满足，证明出现分叉，跳出循环
break;
}
}
return res;
}
}
思路：
一开始我的想法是，遍历二叉树，分别找到p和q节点并记录寻找过程中的路径pPath和qPath，并从头开始遍历两个路径，当开始出现路径不一致的值时，上一个值就是最近公共祖先。代码如下：
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
List<TreeNode> pPath = this.findPath(root, p);
List<TreeNode> qPath = this.findPath(root, q);
int size = Math.min(pPath.size(), qPath.size());
TreeNode res = root;
for (int i = 1; i < size; i++) {
if (pPath.get(i).val == qPath.get(i).val) {
res = pPath.get(i);
}else{
break;
}
}
return res;
}
/**
* 获取从根节点到node节点的寻找路径
* @param root
* @param node
* @return
*/
private List<TreeNode> findPath(TreeNode root, TreeNode node) {
List<TreeNode> path = new ArrayList<>();
TreeNode temp = root;
path.add(root);
while (temp.val != node.val) {
if (node.val > temp.val) {
//往右子树找
temp = temp.right;
} else {
//往左子树找
temp = temp.left;
}
path.add(temp);
}
return path;
}
}
这个方法可以解决问题，但是存在多次遍历，且因为记录了路径值，所以效率不高而且内存占用还大。
在上述寻找路径的代码中，考虑到提供的是一个二叉搜索树，所以使用了二叉搜索树的特性来优化搜索效率。
二叉搜索树的特性：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树。
于是乎我想到，可以使用一次遍历即可解决问题。因为对于p和q的最近公共祖先节点r来说，p和q一定分散在r的两边，即出现分叉。那么我们根据这个条件一次遍历即可找到结果。具体参考开头的代码。
