本來不打算寫的哈哈哈但是發現這一道遞歸我是有思路的！！自己能想到一些方向！我真棒！所以記錄一下哈哈哈

我的思路：

1、祖先一定是自身或往上找，所以如何逆著走呢？

2、3種情況：

有一個結點是另一個結點父節點 ，那么返回其中一個結點本身；

這兩個結點是兄弟結點，那么返回他們的父親結點；（回到上一個問題，怎么找父節點？）；

不是父子也不是兄弟，那么就繼續往上找。

方法一：遞歸

看了題解發現，我想的3種情況中，2和3可以合并，也就是往上找的情況。看這個題解是否能明白呢？

因為樹的遍歷是從上往下，所以方便地遞歸判斷其左右子樹，因此解題方法需要立足于從上往下，這和我的思路的不同的。?

?代碼：

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(!root)return NULL;if(root==p||q==root)return root;TreeNode* leftnode=lowestCommonAncestor(root->left,p,q);TreeNode* rightnode=lowestCommonAncestor(root->right,p,q);if(rightnode&&leftnode)return root;if(leftnode)return leftnode;if(rightnode)return rightnode;//如何判斷left或right就是最近的點呢？return NULL;}

和官方題解的不太一樣哈哈哈，我個人比較習慣這種寫法

方法二：

真的可以存儲父節點欸！用dfs遍歷！?是個很奇妙的思路！

代碼：

class Solution {
public:unordered_map<int,TreeNode*>fa;//存儲父節點unordered_map<int,bool>vis;//一個結點的父節點是否是另一個結點的父節點void dfs(TreeNode* root){if(root->left){fa[root->left->val]=root;dfs(root->left);}//把左子樹都記錄下父節點if(root->right){fa[root->right->val]=root;dfs(root->right);}}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(!root)return NULL;dfs(root);//遍歷，記錄哈希表while(p!=NULL){vis[p->val]=true;p=fa[p->val];}//遍歷p的所有父節點while(q!=NULL){if(vis[q->val])return q;q=fa[q->val];}return NULL;}
};

遞歸加油！！！！再堅持一下！！！