두 갈래 나무 두 노드의 최근 공공 부모 노드를 구하는 두 가지 방법 (java 실현)

public static TreeNode lowestCommenAncestor(TreeNode root,TreeNode p,TreeNode q){
        List<TreeNode> listP = getPath(root,p);
        List<TreeNode> listQ = getPath(root,q);
        HashSet<TreeNode> set = new HashSet<>();
        for(int i = 0;i < listP.size();i ++)
            set.add(listP.get(i));
        for (int i = 0; i < listQ.size(); i++) {
            if(set.contains(listQ.get(i)))
                return listQ.get(i);
        }
        return null;
    }

    // root p 
    public static List<TreeNode> getPath(TreeNode root, TreeNode p){
        List<TreeNode> list = new LinkedList<>();
        isContainsNode(root, p,list);
        return list;
    }

    // ， List 
    public static boolean isContainsNode(TreeNode root, TreeNode p,List<TreeNode> list){
        if(root == null)
            return false;
        if(root == p){
            list.add(p);
            return true;
        }
        else if(isContainsNode(root.left,p,list) || isContainsNode(root.right,p,list)){
                list.add(root);
                return true;
            }
        return false;
    }

 public static TreeNode lowestCommenAncestor2(TreeNode root,TreeNode p,TreeNode q){
        if(root == null || root == p || root == q)
            return root;
        TreeNode left = lowestCommenAncestor2(root.left,p,q);
        TreeNode right = lowestCommenAncestor2(root.right,p,q);
        if(left != null && right != null)
            return root;
        return left != null ? left : right;
    }

    public static void main(String[] args) {
        // 
//                   1
//                /     \
//              2         3
//            /    \    /    \
//           4      5  6      7

        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right = new TreeNode(3);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);
        //4 5 
        System.out.println(lowestCommenAncestor(root,root.left.left,root.left.right).val);
        System.out.println(lowestCommenAncestor2(root,root.left.left,root.left.right).val);
        //2 7 
        System.out.println(lowestCommenAncestor(root,root.left,root.right.right).val);
        System.out.println(lowestCommenAncestor2(root,root.left,root.right.right).val);
    }