[ 题目描述 ]：

[ 思路 ]：

• 两个节点的最近公共祖先具有以下特点
• 如果祖先节点不是自身，那么两个节点一定在祖先节点的两边
• 所以可以递归搜索树的左右子树，如果节点分布在两边，那么这个就是最近公共祖先，如果两个节点分布在同一侧，那么沿着这一侧进行继续搜索
• 运行如下
  

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

[ 官方题解 ]：

• 方法一：递归，基本同上
• 方法二：存储父节点，用哈希表存储所有节点的父节点，然后我们就可以利用节点的父节点信息从 p 结点开始不断往上跳，并记录已经访问过的节点，再从 q 节点开始不断往上跳，如果碰到已经访问过的节点，那么这个节点就是我们要找的最近公共祖先