二叉树最近公共祖先

import java.util.*;
class Solution {
   public boolean getPath(TreeNode root, TreeNode node,
        Deque<TreeNode> stack) {
        if(root == null || node == null)return false;
        stack.push(root);
        //放完之后 要检查
        if(root == node) return true;
        boolean ret1 = getPath(root.left,node,stack);
        if(ret1) return true;
        boolean ret2 = getPath(root.right,node,stack);
        if(ret2) return true;
        stack.pop();
        return false;
    }
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    //1、两个栈当中 存储好数据
    Deque<TreeNode> stack1 = new LinkedList<>();
    getPath(root,p,stack1);
    Deque<TreeNode> stack2 = new LinkedList<>();
    getPath(root,q,stack2);
    //2、判断栈的大小
    int size1 = stack1.size();
    int size2 = stack2.size();
    int len = size1 - size2;
    if(size1 > size2){
        while(len > 0){
            stack1.pop();
            len--;
        }
    } else {
        len = size2 -size1;
        while(len > 0){
            stack2.pop();
            len--;
        }
    }
    while(stack1.peek() != stack2.peek()){
        stack1.pop();
        stack2.pop();
    }
    return stack1.peek();
    }
}