LeetCode 1650. 二叉树的最近公共祖先 III

Categories:

题目描述
思路分析
1. 解法一：双指针（推荐）
2. 解法二：哈希表记录祖先路径
相似题目

题目描述

✅ 1650. 二叉树的最近公共祖先 III

思路分析

解法一：双指针（推荐）

核心思路：

每个节点含有 parent 指针，问题转化为”两个链表找公共节点”

设指针 p 从节点 p 出发，q 从节点 q 出发，分别向上遍历

当 p 到达根节点（null）后，跳到 q 的起点；q 同理跳到 p 的起点

两指针走过相同步数后必然在 LCA 相遇（类似链表相交问题）

复杂度分析：

时间复杂度：O(h)，其中 h 表示树的高度

空间复杂度：O(1)，只用两个指针

class Solution {

  public Node lowestCommonAncestor(Node p, Node q) {
    Node a = p;
    Node b = q;

    // 两指针同速向上，到达 null 后跳到对方起点
    while (a != b) {
      a = (a == null) ? q : a.parent;
      b = (b == null) ? p : b.parent;
    }

    return a;
  }
}

func lowestCommonAncestor(p *Node, q *Node) *Node {
    a, b := p, q

    // 两指针同速向上，到达 null 后跳到对方起点
    for a != b {
        if a == nil {
            a = q
        } else {
            a = a.Parent
        }
        if b == nil {
            b = p
        } else {
            b = b.Parent
        }
    }

    return a
}

解法二：哈希表记录祖先路径

核心思路：

先将节点 p 的所有祖先（含自身）存入哈希集合

再从节点 q 向上遍历，第一个出现在集合中的节点即为 LCA

复杂度分析：

时间复杂度：O(h)，其中 h 表示树的高度

空间复杂度：O(h)，哈希集合存储祖先路径

class Solution {

  public Node lowestCommonAncestor(Node p, Node q) {
    Set<Node> ancestors = new HashSet<>();

    // 记录 p 的所有祖先
    Node cur = p;
    while (cur != null) {
      ancestors.add(cur);
      cur = cur.parent;
    }

    // 从 q 向上找第一个公共祖先
    cur = q;
    while (cur != null) {
      if (ancestors.contains(cur)) {
        return cur;
      }
      cur = cur.parent;
    }

    return null;
  }
}

func lowestCommonAncestor(p *Node, q *Node) *Node {
    ancestors := make(map[*Node]bool)

    // 记录 p 的所有祖先
    for cur := p; cur != nil; cur = cur.Parent {
        ancestors[cur] = true
    }

    // 从 q 向上找第一个公共祖先
    for cur := q; cur != nil; cur = cur.Parent {
        if ancestors[cur] {
            return cur
        }
    }

    return nil
}

相似题目

题目	难度	考察点
236. 二叉树的最近公共祖先	中等	树、递归
235. 二叉搜索树的最近公共祖先	中等	BST、递归
1676. 二叉树的最近公共祖先 IV	中等	树、哈希表
160. 相交链表	简单	双指针、链表
1123. 最深叶节点的最近公共祖先	中等	树、递归
2096. 从二叉树一个节点到另一个节点每一步的方向	中等	树、LCA

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/96117663