最近公共祖先

https://www.lintcode.com/problem/lowest-common-ancestor-of-a-binary-tree/description
给定一棵二叉树，找到两个节点的最近公共父节点(LCA)。

最近公共祖先是两个节点的公共的祖先节点且具有最大深度。
假设给出的两个节点都在树中存在

class Solution {
public:
    /*
     * @param root: The root of the binary search tree.
     * @param A: A TreeNode in a Binary.
     * @param B: A TreeNode in a Binary.
     * @return: Return the least common ancestor(LCA) of the two nodes.
     */
    TreeNode * lowestCommonAncestor(TreeNode * root, TreeNode * A, TreeNode * B) {
        // write your code here
        vector<TreeNode *> vecA;
        preOrder(vecA, root, A);
        vector<TreeNode *> vecB;
        preOrder(vecB, root, B);
        
        TreeNode *res = NULL;
        
        for (int i = 0; i < vecA.size() && i < vecB.size(); i++) {
            if (vecA[i] == vecB[i]) {
                res = vecA[i];
            } else {
                break;
            }
        }
        
        return res;
    }
    
    bool preOrder(vector<TreeNode *> &vec, TreeNode * root, TreeNode *node) {
        if (root == NULL) {
            return false;
        }
        
        if (root == node) {
            vec.push_back(node);
            return true;
        }
        
        vec.push_back(root);
        
        if (preOrder(vec, root->left, node)) {
            return true;
        }

        if (preOrder(vec, root->right, node)) {
            return true;
        }
        
        vec.pop_back();
        return false;
    }
};

引：https://www.cnblogs.com/theskulls/p/5135898.html
最近公共祖先 II：
https://www.lintcode.com/problem/lowest-common-ancestor-ii/description?_from=ladder&&fromId=53
最近公共祖先 III：
https://www.lintcode.com/problem/lowest-common-ancestor-iii/description