首頁 盲人摸象 数据结构

# 题目

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

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

binarytree

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

输入：root = [1,2], p = 1, q = 2
输出：1

好笨啊，看看题解吧

# 递归

Moment

当我们用递归去做这个题时不要被题目误导，应该要明确一点
这个函数的功能有三个：给定两个节点 p 和 q

  • 如果 p 和 q 都存在，则返回它们的公共祖先；
  • 如果只存在一个，则返回存在的一个；
  • 如果 p 和 q 都不存在，则返回 NULL

本题说给定的两个节点都存在，那自然还是能用上面的函数来解决

具体思路

  1. 如果当前结点 root 等于 NULL，则直接返回 NULL
  2. 如果 root 等于 p 或者 q ，那这棵树一定返回 p 或者 q
  3. 然后递归左右子树，因为是递归，使用函数后可认为左右子树已经算出结果，用 left 和 right 表示
  4. 此时若 left 为空，那最终结果只要看 right；若 right 为空，那最终结果只要看 left
  5. 如果 left 和 right 都非空，因为只给了 p 和 q 两个结点，都非空，说明一边一个，因此 root 是他们的最近公共祖先
  6. 如果 left 和 right 都为空，则返回空（其实已经包含在前面的情况中了）

时间复杂度是 O (n)：每个结点最多遍历一次或用主定理，空间复杂度是 O (n)：需要系统栈空间

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == NULL)
            return NULL;
        if(root == p || root == q) 
            return root;
            
        TreeNode* left =  lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
       
        if(left == NULL)
            return right;
        if(right == NULL)
            return left;      
        if(left && right) //p 和 q 在两侧
            return root;
        
        return NULL; // 必须有返回值
    }
};

# 暴力

old8

一次 dfs 维护出每个点的深度和父亲，查询时先将两点定到相同深度，之后一起往上跳。整体复杂度为 O (nlogn)。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
  TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    map<TreeNode*, int> vis;
    map<TreeNode*, TreeNode*> pre;
    function<void(TreeNode*, TreeNode*, int)> dfs = [&](TreeNode* fa, TreeNode* rt, int dep) {
      vis[rt] = dep;
      pre[rt] = fa;
      if (rt->left) dfs(rt, rt->left, dep + 1);
      if (rt->right) dfs(rt, rt->right, dep + 1);
    };
    dfs(NULL, root, 1);
    
    if (p == q) return p;
    while (vis[p] > vis[q] && pre[p] != NULL) p = pre[p];
    while (vis[p] < vis[q] && pre[q] != NULL) q = pre[q];
    while (p != q) {
      p = pre[p];
      q = pre[q];
    }
    return p;
  }
};
# 倍增优化 DP
维护 f (u, k) 表示 u 节点的第2k2^k 个祖先，更新时一次 dfs，f (u, k + 1) = f (f (u, k), k)，查询的时候类似暴力解法，不过向上跳可以跳得步伐大很多。对于本题预处理复杂度为 O (nlogn)，查询复杂度为 O (2logn)。
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
  TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    const int maxf = 22;
    map<TreeNode*, int> vis;
    map<TreeNode*, TreeNode*> pre[maxf];
    function<void(TreeNode*, TreeNode*, int)> dfs = [&](TreeNode* fa, TreeNode* rt, int dep) {
      vis[rt] = dep;
      pre[0][rt] = fa;
      for (int i = 0; (1 << i) <= vis[fa] && i < maxf; i++) {
        pre[i + 1][rt] = pre[i][pre[i][rt]];
      }
      if (rt->left) dfs(rt, rt->left, dep + 1);
      if (rt->right) dfs(rt, rt->right, dep + 1);
    };
    dfs(NULL, root, 1);
    if (vis[p] < vis[q]) swap(p, q);
    for (int i = maxf - 1; i >= 0; i--) {
      if (vis[p] >= (1 << i) && vis[pre[i][p]] >= vis[q]) p = pre[i][p];
      if (p == q) return p;
    }
    for (int i = maxf - 1; i >= 0; i--) {
      if (vis[p] >= (1 << i) && pre[i][p] != pre[i][q]) {
        p = pre[i][p];
        q = pre[i][q];
      }
    }
    return pre[0][p];
  }
};
# 思考
Krahets
何为最近公共祖先？
设节点 root 为节点 p，q 的某公共祖先，若其左子节点 root.left 和右子节点 root.right 都不是 p，q 的公共祖先，则称 root 是 “最近的公共祖先”
根据以上定义，若 root 是 p，q 的最近最近公共祖先，则只可能为以下的情况之一：
  1. p，q 位于 root 异侧（分别在左右子树中）
  2. p = root，且 q 在 root 的左或右子树中
  3. q = root，且 p 在 root 的左或右子树中
比如，上图中的 7，8，它们的最近公共祖先为 3，因为 5 不是 8 的祖先，1 不为 7 的祖先。
递归解析
  • 终止条件
    • 当越过叶节点，直接返回 null；
    • 当 root 等于 p，q，则直接返回 root；
  • 递归工作
    • 开启递归左子节点，返回值记为 left；
    • 开启递归右子节点，返回值即为 right；
  • 返回值：
    • 当 left 和 right 同为空，说明 root 的左 / 右子树中均不含 p，q，则返回 null；
    • 当 left 和 right 同不为空，说明 p，q 分别位于 root 异侧，因此 root 为最近公共祖先，返回 root；
    • 当 left 为空，right 不为空，p，q 都不在 root 的左子树中，直接返回 right，具体有两种情况：
      1. p，q 其中一个在 root 的右子树中，此时 right 指向 p（假设为 p）；
      2. p，q 两节点都在 root 的右子树中，此时的 right 指向最近公共祖先节点；
    • 当 left 不为空，right 为空，与前一种情况同理
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == nullptr || root == p || root == q) return root;
        TreeNode *left = lowestCommonAncestor(root->left, p, q);
        TreeNode *right = lowestCommonAncestor(root->right, p, q);
        if(left == nullptr && right == nullptr) return nullptr; // 1.
        if(left == nullptr) return right; // 3.
        if(right == nullptr) return left; // 4.
        return root; // 2. if(left != null and right != null)
    }
};
/* 观察发现， 情况 1. 可合并至 3. 和 4. 内 */
// class Solution {
// public:
//     TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
//         if(root == nullptr || root == p || root == q) return root;
//         TreeNode *left = lowestCommonAncestor(root->left, p, q);
//         TreeNode *right = lowestCommonAncestor(root->right, p, q);
//         if(left == nullptr) return right;
//         if(right == nullptr) return left;
//         return root;
//     }
// };
  • 时间复杂度 O (N) ： 其中 NN 为二叉树节点数；最差情况下，需要递归遍历树的所有节点。
  • 空间复杂度 O (N) ： 最差情况下，递归深度达到 N ，系统使用 O (N) 大小的额外空间。