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

心路历程：

其实，最主要是没有意识到只要是二叉搜索树，意味着就有明确唯一快速的路径，到底目标节点，知道了各自的路径，就可以快速找到公共的祖先了！

解题思路：

方法一：记录路径，找共同起点的方法

1）实现getPath的方法，找到节点在二叉树的路径

2）对比路径path列表就可以找到，公共祖先了

方法二：通过挪动TreeNode快速找到公共祖先

原理：因为是二叉搜索树，就可以跟当前遍历的节点值做比对：

1）若q、p的值在当前节点的两边，就说明它就是公共祖先

2）若q、p的值在当前节点左边，就说明公共节点在左边，节点递归到当前左子节点

3）若q、p的值在当前节点右边，就说明公共节点在右边，节点递归到当前右子节点

import java.util.*;


public class Solution {

    public int lowestCommonAncestor (TreeNode root, int p, int q) {
        if (root == null) {
            return  -1;
        }
        if ((p >= root.val && q <= root.val) || (p <= root.val && q >= root.val)) {
            return root.val;
        } else if (p <= root.val && q <= root.val) {
            return lowestCommonAncestor(root.left, p, q);
        } else {
            return lowestCommonAncestor(root.right, p, q);
        }
    }


    public ArrayList<Integer> findPath(TreeNode root, int target) {
        ArrayList<Integer> path = new ArrayList<Integer>();
        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;
    }
    /**
     *
     * @param root TreeNode类
     * @param p int整型
     * @param q int整型
     * @return int整型
     */
    public int lowestCommonAncestor2 (TreeNode root, int p, int q) {
        ArrayList<Integer> pPath = findPath(root, p);
        ArrayList<Integer> qPath = findPath(root, q);

        int res = 0;
        for (int i = 0; i < qPath.size() && i < pPath.size(); i++) {
            int x = qPath.get(i);
            int y = pPath.get(i);
            if (x == y) {
                res = pPath.get(i);
            } else {
                break;
            }
        }
        return res;
    }


}