public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if(root == null) return null;

    // p 為當(dāng)前樹(shù)的根節(jié)點(diǎn)
    if(p == root) return p;
    // q 為當(dāng)前樹(shù)的根節(jié)點(diǎn)
    if(q == root) return q;
    
    // 去左子樹(shù)中找
    TreeNode left = lowestCommonAncestor(root.left,p,q);
    // 去右子樹(shù)中找
    TreeNode right = lowestCommonAncestor(root.right,p,q);

    // 左邊右邊都找到了
    if(left != null && right != null) {
        return root;
    }
    // 左邊找到了，右邊沒(méi)找到
    if(left != null) {
        return left;
    }
    if(right != null) {
        return right;
    }
    return null;
}

// 用于找節(jié)點(diǎn)的路徑
public boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack) {
    if(root == null || node == null) {
        return false;
    }
    // 將當(dāng)前節(jié)點(diǎn)放入棧中
    stack.push(root);
    
    if(root.val == node.val) {
        return true;// 找到了
    }
    // 當(dāng)前節(jié)點(diǎn)沒(méi)找到，去左子樹(shù)找
    boolean flag = getPath(root.left,node,stack);
    // 左子樹(shù)中找到了，直接返回
    if(flag) {
        return true;
    }
    // 左子樹(shù)沒(méi)找到，去右子樹(shù)找
    flag = getPath(root.right,node,stack);
    // 右子樹(shù)中找到了，直接返回
    if(flag) {
        return true;
    }
    
    // 左右子樹(shù)都沒(méi)找到，彈出節(jié)點(diǎn)
    stack.pop();
    return false;

}
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if(root == null) {
        return null;
    }
    Stack<TreeNode> stackp = new Stack<>();
    Stack<TreeNode> stackq = new Stack<>();

    // 分別得到  p q 的路徑
    getPath(root,p,stackp);
    getPath(root,q,stackq);

    int sizep = stackp.size();
    int sizeq = stackq.size();

    if(sizep > sizeq) {
        int size = sizep - sizeq;
        // 彈出元素直至兩棧中元素個(gè)數(shù)相等
        while(size > 0) {
            stackp.pop();
            size--;
        }
    }else {
        int size = sizeq - sizep;
        // 彈出元素直至兩棧中元素個(gè)數(shù)相等
        while(size > 0) {
            stackq.pop();
            size--;
        }
    }

    // 一起彈出，直到找到第一個(gè)相同的元素
    while(!stackp.isEmpty() && !stackq.isEmpty()) {
        if(stackp.peek() == stackq.peek()) {
        	// 找到了，就返回該節(jié)點(diǎn)
            return stackq.pop();
        }else {
            stackp.pop();
            stackq.pop();
        }
    }
    // 沒(méi)找到，返回 null
    return null;
}