526互联

LeetCode 236_ 二叉树的最近公共祖先

发布时间 2023-06-02 14:42:31作者: 穿过雾的阴霾
class Solution {
public:
    vector<TreeNode*> path1,path2;
    bool dfs(TreeNode* root,TreeNode* p,vector<TreeNode*>& path)
    {
        if(!root)   return false;
        if(root==p||dfs(root->left,p,path)||dfs(root->right,p,path))
        {
            path.push_back(root);
            return true;
        }
        return false;
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        dfs(root,p,path1);
        dfs(root,q,path2);
        reverse(path1.begin(),path1.end());
        reverse(path2.begin(),path2.end());
        TreeNode* res;
        for(int i=0;i<path1.size()&&i<path2.size();i++)
            if(path1[i]==path2[i])   res=path2[i];
        return res;
    }
};