题目：
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
示例 1:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 输出: 6 解释: 节点2和节点8的最近公共祖先是6。
示例 2:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4 输出: 2 解释: 节点2和节点4的最近公共祖先是2, 因为根据定义最近公共祖先节点可以为节点本身。
说明:
- 所有节点的值都是唯一的。
- p、q 为不同节点且均存在于给定的二叉搜索树中。
代码：
//此方法不只是求解二叉搜索树时可用，非搜索树也可
1 /**
2 * Definition for a binary tree node.
3 * public class TreeNode {
4 * int val;
5 * TreeNode left;
6 * TreeNode right;
7 * TreeNode(int x) { val = x; }
8 * }
9 */
10 class Solution {
11 //记录路径和是否已找到要找的结点
12 static ArrayList<TreeNode> arrayList=new ArrayList<>();
13 static boolean bool=false;
14 public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
15 //每次遍历寻找都要的重置
16 arrayList.clear();
17 bool=false;
18
19 backTrack(root,p);
20 List<TreeNode> list1=new ArrayList<>(arrayList);
21
22 arrayList.clear();
23 bool=false;
24
25 backTrack(root,q);
26 List<TreeNode> list2=new ArrayList<>(arrayList);
27 int len1=list1.size();
28 int len2=list2.size();
29 int i=0;
30 //找到的第一个不同说明上一个是最后一个共同结点，如果某一方遍历结束还是都相同，那么结束的一方是未结束一方的父节点，只需要输出结束一方的尾节点
31 for ( i = 0; i <len1&&i<len2 ; i++) {
32 if(list1.get(i)!=list2.get(i)){
33 return list1.get(i-1);
34 }
35 }
36 if(i==len1){
37 return list1.get(len1-1);
38 }else{
39 return list2.get(len2-1);
40 }
41 }
42 //寻找从根抵达目标节点的路径方法
43 public static void backTrack(TreeNode root,TreeNode p){
44 if(bool!=true) {
45 if (root == p) {
46 bool=true;
47 arrayList.add(root);
48 }else{
49 arrayList.add(root);
50 if(root.left!=null&&bool!=true){
51 backTrack(root.left,p);
52 }
53 if(root.right!=null&&bool!=true){
54 backTrack(root.right,p);
55 }
56 if(bool!=true){
57 arrayList.remove(root);
58 }
59
60 }
61
62 }
63 }
64
65 }
代码：
//此方法来自题解
1 /**
2 * Definition for a binary tree node.
3 * public class TreeNode {
4 * int val;
5 * TreeNode left;
6 * TreeNode right;
7 * TreeNode(int x) { val = x; }
8 * }
9 */
10 class Solution {
11
12 public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
13
14 if(root==null){return null;}
15 if(root.val<p.val&&root.val<q.val){
16 return lowestCommonAncestor(root.right,p,q);
17 }
18 if(root.val>p.val&&root.val>q.val){
19 return lowestCommonAncestor(root.left,p,q);
20 }
21 return root;
22 }
23
24 }