/**
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
class Solution {
private:
unordered_map<int, TreeNode*>ret;
public:
/**
*
* @param root TreeNode类
* @param o1 int整型
* @param o2 int整型
* @return int整型
*/
int lowestCommonAncestor(TreeNode* root, int o1, int o2) {
// write code here
vector<int>path;
dfs(root);
ret[root->val]=nullptr;
TreeNode*oo1=ret[o1];
TreeNode*oo2=ret[o2];
path.emplace_back(o1);
while(oo1){
path.emplace_back(oo1->val);
oo1=ret[oo1->val];
}
while(oo2){
if(find(path.begin(),path.end(),o2)!=path.end())return o2;
if(find(path.begin(),path.end(),oo2->val)!=path.end())return oo2->val;
oo2=ret[oo2->val];
}
return -1;
}
void dfs(TreeNode*root){
if(root->left){
ret[root->left->val]=root;
dfs(root->left);
}
if(root->right){
ret[root->right->val]=root;
dfs(root->right);
}
}
};
此题目关键是获取父节点的节点,因此可以深度遍历然后反向遍历。