class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        List<TreeNode> a = getPath(root, p.val);
        List<TreeNode> b = getPath(root, q.val);
        int i = 0;
        while (i < a.size() && i < b.size() && a.get(i).val == b.get(i).val) {
            i += 1;
        }
        return a.get(i - 1);
    }

    List<TreeNode> getPath(TreeNode root, int target) {
        if (root.val == target) {
            LinkedList<TreeNode> path = new LinkedList<>();
            path.add(root);
            return path;
        }
        List<TreeNode> path = getPath(root.val < target ? root.right : root.left, target);
        path.add(0, root);
        return path;
    }
}

class Solution {
    public List<TreeNode> getPath(TreeNode root, TreeNode target) {
        List<TreeNode> path = new ArrayList<TreeNode>();
        TreeNode node = root;
        while (node != target) {
            path.add(node);
            if (target.val < node.val) {
                node = node.left;
            } else {
                node = node.right;
            }
        }
        path.add(node);
        return path;
    }
}

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode low, high;
        if (p.val > q.val) {
            low = q;
            high = p;
        } else {
            low = p;
            high = q;
        }
        while (true) {
            if (root.val > high.val) {
                root = root.left;
            } else if (root.val < low.val) {
                root = root.right;
            } else {
                return root;
            }
        }
    }
}

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        return (root.val - p.val) * (root.val - q.val) <= 0 ? root : lowestCommonAncestor(p.val < root.val ? root.left : root.right, p, q);
    }
}