/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */


 /*
    方法一 后序遍历非递归，分别查找中根节点到p,q的路径，再进行匹配
     vector<TreeNode*> findPath(TreeNode* root,TreeNode* p)
    {
        vector<TreeNode*> s;
        TreeNode* cur=root;
        TreeNode* pre=NULL;

        s.push_back(cur);
        while(cur || s.size())
        {
            while(cur)
            {
                s.push_back(cur);
                cur=cur->left;

            }
            cur=s.back();
            if(cur->right && cur->right!=pre)
                cur=cur->right;
            else
            {
                if(cur==p)
                    return s;
                s.pop_back();
                pre=cur;
                cur=NULL;
            }
        }
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        vector<TreeNode*> path1=findPath(root,p);
        vector<TreeNode*> path2=findPath(root,q);

        if(path1.size()>path2.size()) swap(path1,path2);

        for(int i=0;i<path1.size();i++)
        {
            if(path1[i]!=path2[i])
                return path1[i-1];
        }
        return path1.back();
    }
 */

 /*
    方法二 采用递归，当p和q分别位于左右子树中，则root为最近祖先节点，
    当p和q都在右子树时，则最近祖先节点在右子树上

 */
class Solution {
public:

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root) return NULL;
        if(root==p || root==q)
            return root;
        TreeNode* left=lowestCommonAncestor(root->left,p,q);
        TreeNode* right=lowestCommonAncestor(root->right,p,q);
        if(left&&right)
            return root;
        if(left==NULL)
            return right;
        else
            return left;
    }
};