68(2)-二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

与上一题的关键不同就在于这次仅仅是二叉树，而不是平衡二叉树，就无法确定往哪个方向找了。

栈方法

我们可以参考两个链表的公共节点题目的解法，比如上图3和1的公共节点，除了链表指向是反的，实际就是两个链表公共的节点问题。我们可以用栈反转顺序。

1. 先找到这两个节点，将节点使用栈保存，这样栈的顺序就保证了出栈时是从节点到root节点，由下到上的。
2. 先让路径长的多走几步
3. 两个栈并驾齐驱的弹出数据，直到相等。

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        Stack<TreeNode> pPath = searchPath(root, p.val);
        Stack<TreeNode> qPath = searchPath(root, q.val);
        if (pPath.size() != qPath.size()) {
            Stack<TreeNode> longerPath = pPath.size() > qPath.size() ? pPath : qPath;
            int gap = Math.abs(pPath.size() - qPath.size());
            for (int i = 0; i < gap; i++) {
                longerPath.pop();
            }
        }
        while (true) {
            if (pPath.peek().val == qPath.peek().val) {
                return pPath.pop();
            }else{
                pPath.pop();
                qPath.pop();
            }
        }
    }

    private Stack<TreeNode> searchPath(TreeNode root, int val){
        Stack<TreeNode> stack = new Stack<>();
        searchPathCore(stack, root, val);
        return stack;
    }
    private boolean searchPathCore(Stack<TreeNode> stack,TreeNode root, int val){
        if (root == null) {
            return false;
        }
        stack.add(root);
        if (root.val == val) {
            return true;
        }
        boolean inLeft = searchPathCore(stack, root.left, val);
        if(inLeft){
            return true;
        }
        boolean inRight = searchPathCore(stack, root.right, val);
        if (inRight) {
            return true;
        }
        stack.pop();
        return false;
    }

递归解法

 public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root == p || root == q) return root;
        TreeNode left = lowestCommonAncestor2(root.left, p, q);
        TreeNode right = lowestCommonAncestor2(root.right, p, q);
        if(left == null) return right;
        if(right == null) return left;
        return root;
    }