最近公共父节点

1，排序二叉树

p<最近父节点<q

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==NULL) return root;
        TreeNode *t=root;
        while(1){
            if(t->val>p->val && t->val>q->val)
                t=t->left;
            else if(t->val<p->val && t->val<q->val)
                t=t->right;
            else
                return t;
        }
    }

2，带指向父节点的二叉树

从这两个节点回溯到根节点，得到两条路径，转化为求两个链表的第一个公共节点

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==NULL) return root;
        
        vector<TreeNode*> a1,a2;
        TreeNode* t=p;
        while(t!=root){
            a1.push_back(t);
            t=t->pre;
        }
        a1.push_back(root);

        t=q;
        while(q!=root){
            a2.push_back(t);
            t=t->pre;
        }
        a2.push_back(root);

        int len1=a1.size(),len2=a2.size();
        int i=0,j=0;
        if(len1>len2)
            i=len1-len2;
        else
            j=len2-len1;
        for(;i<len1&&j<len2;i++,j++){
            if(a1[i]==a2[j])
                return a1[i];
        }

    }

3，二叉树

递归:
该函数：若以root为根，包含p，q，返回最近父节点；若只包含一个p或q，返回p或q；若都不包含，返回NULL。时间O(n)

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==NULL)
            return NULL;
        if(p=root || q=root)
            return root;

        TreeNode *left = lowestCommonAncestor(root->left, p, q);
        TreeNode *right = lowestCommonAncestor(root->right, p, q);
        if(left && right) 
            return root; 
        else
            return left? left:right;
    }

非递归：
定义一个子函数findPath()寻找两条路径，再转化为求两个链表的第一个公共节点。时间O(n)

bool findPath(TreeNode* root,TreeNode* p,stack<TreeNode*> &path)
{
    if(root){
        path.push(root);

        if(root==p)
            return true;
             
        bool found=false;
        if(!found)
            found=findPath(root->left,p,path);
        if(!found)
            found=findPath(root->right,p,path);

        if(!found)
            path.pop();  //不是答案时要出栈，是答案时要留栈
        return found;  
    }
    return false;
}