二叉树的最近公共祖先

1.两个结点的公共祖先一定在从根结点，至这两个结点的路径上

2.由于求公共祖先中最近的公共祖先，就是同时出现在这两个结点的两条路径上、离根结点最远的结点

求P结点路径，Q结点路径，两路径上最后一个相同的结点。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        vector<TreeNode*> path;
        vector<TreeNode*> p_path;//p结点的路径
        vector<TreeNode*> q_path;
        int finish = 0;
        
        preorder(root,p,path,p_path,finish);     
        
        path.clear();
        finish = 0;        
        preorder(root,q,path,q_path,finish);//得到了两个结点的路径
        
        int len = 0;
        if(p_path.size() <= q_path.size())
            len = p_path.size();
        else
            len = q_path.size();
        
        TreeNode* ancestor = nullptr;
        for(int i =0;i<len;++i)
        {
            if(p_path[i] == q_path[i])
                ancestor = p_path[i];
        }
        
        return ancestor;
    }
    
    //求根结点到某结点路径
    //                当前结点      要搜索的结点        路径                  搜索的路径结果    标志是否找到了目标，1找到，0没找到
    void preorder(TreeNode* node,TreeNode* search,vector<TreeNode*>& path,vector<TreeNode*>& res,int& finish)
    {
        if(node == nullptr || finish == 1)
            return;//如果为空或者找到了，就返回
        
        path.push_back(node);
        if(node == search)
        {
            res = path;
            finish = 1;    
        }
        preorder(node->left,search,path,res,finish);
        preorder(node->right,search,path,res,finish);
        
        path.pop_back();
    }
    
    
};