目标
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。
思路
我第一次想到的方法是先找到这两个指定节点，然后交替求取位置索引较大节点的父节点。然后比较，如果值相等则为公共祖先。但是，题目给出的树结构中不包含指向父节点的引用，很自然地想到先将值保存到数组中，中序遍历二叉搜索树得到正序序列。然后二分查找出index，计算父节点index：左孩是奇数index，父index为(child-1)/2，右孩是偶数index，父index为(child-2)/2，注意排除root，index为0。接着比较父节点的值，还应该考虑输入节点本身就是父子关系的情况，如果pindex > qindex，应先求p节点的父index，因为index大，层数可能更高。再与qindex对应的值比较，不相等的话再求q节点的父index，依此类推。题目中有提到，树中的值都是唯一的。这个想法看起来正确，但真正去实现的时候就会发现是不可行的。首先是存储空间问题，要在数组中保留树的结构，在有许多空节点的情况下是不可行的。这个在 二叉搜索树最近节点查询 中提到过。然后是二分查找需要先排序的问题，这本身就打乱了树节点的index关系。
这几天刷题有一个感受，就是如果算法实现起来太过复杂那么一定是有问题的，很有可能是求解的方向不对。
于是我换了一种思路，还是先找到这两个节点，但是在找的过程中记录下访问的路径，然后再找到路径节点中所有相同节点中的最后一个即可。那么路径应该保存到哪里，又如何获取相同节点序列的最后一个呢？
在 Java 的标准库中，java.util.Stack 类是使用数组实现的。然而，从 Java 6 开始，java.util.Stack 类被标记为遗留（legacy），并建议使用 java.util.Deque 接口及其实现（如 ArrayDeque 或 LinkedList）来替代。Deque 接口表示双端队列，它支持在两端插入和删除元素，因此非常适合实现栈和队列。----AI的回答
无论是使用数组还是链表，最后查找的时候，都可以从头开始同时比较，直到第一个不相等节点出现即可。无需额外申请空间。
如果从尾开始比较的话，需要借助HashSet，将其中一个路径序列存入集合，然后循环弹另一个路径栈，第一个在集合中的被弹出元素就是最近的公共祖先。需要额外的空间。有的时候条件反转一下可以简化处理逻辑，而有时则相反！
另外数组长度固定，超过的话就会有重新分配空间的开销。
代码
public TreeNode lowestCommonAncestor_v1(TreeNode root, TreeNode p, TreeNode q) {
Stack<TreeNode> pStack = findPath(root, p.val, new Stack<>());
Stack<TreeNode> qStack = findPath(root, q.val, new Stack<>());
HashSet<Integer> set = new HashSet<>();
while (!pStack.empty()){
set.add(pStack.pop().val);
}
TreeNode res = null;
while (!qStack.empty()){
res = qStack.pop();
if (set.contains(res.val)) {
break;
}
}
return res;
}
public Stack<TreeNode> findPath(TreeNode subRoot, int value, Stack<TreeNode> stack) {
stack.push(subRoot);
if (subRoot.val == value) {
return stack;
} else if (subRoot.val > value) {
return findPath(subRoot.left, value, stack);
} else {
return findPath(subRoot.right, value, stack);
}
}
/**
* 还有一个更好的做法是一次遍历同时比较p,q，如果一个大于等于，一个小于等于 当前节点值，表明已经/准备分叉了
* 这个是看了题解之后发现的
*/
public TreeNode lowestCommonAncestor_v2(TreeNode root, TreeNode p, TreeNode q) {
if (root.val > p.val && root.val > q.val) {
return lowestCommonAncestor_v2(root.left, p, q);
} else if (root.val < p.val && root.val < q.val) {
return lowestCommonAncestor_v2(root.right, p, q);
} else {
return root;
}
}性能
