题解 | #二叉搜索树的最近公共祖先#

如何获取公共祖先？

要获取公共祖先，首先要获得根节点目标节点的路径，要获取路径就需要遍历二叉树将沿途的节点加入路径数组中，而二叉搜索树是有序的，可以根据节点的大小关系选择指针遍历，而不需要循环遍历，因为路径都是从根节点出发，所以两个目标节点的最远公共祖先是根节点，最近目标节点为两个目标节点的路径中最后一个相同的节点。

参考

参考链接

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param p int整型 
     * @param q int整型 
     * @return int整型
     */
    private ArrayList<Integer> getPath(TreeNode root, int target) {
        ArrayList<Integer> path = new ArrayList<>();
        TreeNode node = root;
        // 节点值都不同，可以用值比较判断循环
        // 二叉搜索树不需要递归找路径
        while(node.val != target) {
            path.add(node.val);
            if (target < node.val) {
                node = node.left;
            }
            else {
                node = node.right;
            }
        }
        path.add(node.val);
        return path;
    }
    public int lowestCommonAncestor (TreeNode root, int p, int q) {
        // write code here
        ArrayList<Integer> pathP = getPath(root, p);
        ArrayList<Integer> pathQ = getPath(root, q);
        int res = 0;
        for (int i = 0; i < pathP.size() && i < pathQ.size(); ++i) {
            int x = pathP.get(i);
            int y = pathQ.get(i);
            // 最后一个相同的点就是最近公共祖先
            if (x == y) {
                res = pathP.get(i);
            }
            else {
                break;
            }
		    // 如果换成以下写法就过不了最后一个用例，不知道为什么
		    // if (pathP.get(i) == pathQ.get(i)) {
                // res = pathP.get(i);
            // }
        }
        return res;
    }
}