二叉树的最近公共祖先——递归/深度优先搜索

一、题目

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。

二、思路

1.递归

检查p,q能否在root.left中找到

检查p,q能否在root.right中找到

若1满足，2不满足，则最近公共节点为root.left

若1不满足，2满足，则最近公共节点为root.right

若1满足&2满足，则最近公共节点为root

2.存储父节点

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

1）从根节点开始遍历整棵二叉树，用哈希表记录每个节点的父节点指针。

2）从 p 节点开始不断往它的祖先移动，并用数据结构记录已经访问过的祖先节点。

3）同样，我们再从 q 节点开始不断往它的祖先移动，如果有祖先已经被访问过，即意味着这是 p 和 q 的深度最深的公共祖先，即 LCA 节点。

3.简单便捷思路

两个节点的情况有两种，一种是在同一棵子树中，一种是不在同一棵子树中。

从根节点遍历，递归向左右子树查找节点信息。

递归终止条件，如果当前节点找到或者节点为空，则返回。

1)递归遍历左右子树，如果左右子树查到节点都不为空，则表明 p 和 q 分别在左右子树中，因此，当前节点即为最近公共祖先；

2)如果左右子树其中一个不为空，则返回非空节点。

三、知识点

1.二叉树和二叉搜索树的关系

二叉树：每个结点最多 2 棵子树，没有其它限制了。

二叉查找树：也叫 二叉搜索树，首先它是二叉树，并且 左子树上所有结点的值 小于 它根结点的值，右子树上所有结点的值 大于 它根结点的值。

二叉排序树：就是二叉查找树。

2.哈希表

3.深度优先搜索

四、代码

1.递归C++

class Solution {public:TreeNode* ans;bool dfs(TreeNode* root, TreeNode* p, TreeNode* q) {if (root == nullptr) return false;bool lson = dfs(root->left, p, q);bool rson = dfs(root->right, p, q);if ((lson && rson) || ((root->val == p->val || root->val == q->val) && (lson || rson))) {ans = root;} return lson || rson || (root->val == p->val || root->val == q->val);}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {dfs(root, p, q);return ans;}};

2.存储父节点C++

class Solution {public:unordered_map<int, TreeNode*> fa;unordered_map<int, bool> vis;void dfs(TreeNode* root){if (root->left != nullptr) {fa[root->left->val] = root;dfs(root->left);}if (root->right != nullptr) {fa[root->right->val] = root;dfs(root->right);}}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {fa[root->val] = nullptr;dfs(root);while (p != nullptr) {vis[p->val] = true;p = fa[p->val];}while (q != nullptr) {if (vis[q->val]) return q;q = fa[q->val];}return nullptr;}};

3.简单思路C++

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

五、总结

1.递归复杂度

时间复杂度：O(N)，其中 N 是二叉树的节点数。二叉树的所有节点有且只会被访问一次，因此时间复杂度为 O(N)。

空间复杂度：O(N) ，其中 N是二叉树的节点数。递归调用的栈深度取决于二叉树的高度，二叉树最坏情况下为一条链，此时高度为 N，因此空间复杂度为 O(N)。

2.存储父节点复杂度

时间复杂度：O(N)，其中 N 是二叉树的节点数。二叉树的所有节点有且只会被访问一次，从 p 和 q 节点往上跳经过的祖先节点个数不会超过 N，因此总的时间复杂度为 O(N)。

空间复杂度：O(N) ，其中 N 是二叉树的节点数。递归调用的栈深度取决于二叉树的高度，二叉树最坏情况下为一条链，此时高度为 N，因此空间复杂度为 O(N)，哈希表存储每个节点的父节点也需要 O(N) 的空间复杂度，因此最后总的空间复杂度为 O(N)。

如果觉得《二叉树的最近公共祖先——递归/深度优先搜索》对你有帮助，请点赞、收藏，并留下你的观点哦！