二叉树节点的最近公共祖先

二叉树的一个经典问题是找到两个节点的最近公共祖先。
一个经典解法是找到从根节点到该节点的路径，然后两条路径找公共节点。

private boolean search(TreeNode root, TreeNode target, Deque<TreeNode> deque) {
    if (root == null) {
        return false;
    }
    deque.add(root);
    if (root == target) {
        return true;
    }
    boolean ret = search(root.left, target, deque);
    if (ret) {
        return ret;
    }
    ret = search(root.right, target, deque);
    if (!ret) {
        deque.removeLast();
    }
    return ret;
}

这段找路径的代码使用的算法是先序遍历，需要注意：

1. 空树、单节点、两节点、三节点的单元测试
2. 需要及时退出程序，注意此时deque的入队和出队。
   后续代码：

TreeNode result = null;
while (!deque1.isEmpty() && !deque2.isEmpty()) {
    TreeNode treeNode1 = deque1.removeFirst();
    TreeNode treeNode2 = deque2.removeFirst();
    if (treeNode1 == treeNode2) {
        result = treeNode1;
    } else {
        break;
    }
}
System.out.println(result);