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;
}
};
标签:path2,path1,TreeNode,dfs,二叉树,path,236,root,LeetCode
From: https://www.cnblogs.com/tangxibomb/p/17451709.html