Skip to content

1644. Lowest Common Ancestor of a Binary Tree II 👍

Approach 1: Two variables

  • Time: $O(n)$
  • Space: $O(h)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
 public:
  TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    bool seenP = false;
    bool seenQ = false;
    TreeNode* lca = getLCA(root, p, q, seenP, seenQ);
    return seenP && seenQ ? lca : nullptr;
  }

 private:
  TreeNode* getLCA(TreeNode* root, TreeNode* p, TreeNode* q, bool& seenP,
                   bool& seenQ) {
    if (root == nullptr)
      return nullptr;
    // Need to traverse the entire tree to update `seenP` and `seenQ`.
    TreeNode* left = getLCA(root->left, p, q, seenP, seenQ);
    TreeNode* right = getLCA(root->right, p, q, seenP, seenQ);
    if (root == p) {
      seenP = true;
      return root;
    }
    if (root == q) {
      seenQ = true;
      return root;
    }
    if (left != nullptr && right != nullptr)
      return root;
    return left == nullptr ? right : left;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
  public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    TreeNode lca = getLCA(root, p, q);
    return seenP && seenQ ? lca : null;
  }

  private boolean seenP = false;
  private boolean seenQ = false;

  private TreeNode getLCA(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null)
      return null;
    // Need to traverse the entire tree to update `seenP` and `seenQ`.
    TreeNode left = getLCA(root.left, p, q);
    TreeNode right = getLCA(root.right, p, q);
    if (root == p) {
      seenP = true;
      return root;
    }
    if (root == q) {
      seenQ = true;
      return root;
    }
    if (left != null && right != null)
      return root;
    return left == null ? right : left;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
  def lowestCommonAncestor(
      self,
      root: 'TreeNode',
      p: 'TreeNode',
      q: 'TreeNode',
  ) -> 'TreeNode':
    seenP = False
    seenQ = False

    def getLCA(root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
      nonlocal seenP
      nonlocal seenQ
      if not root:
        return None
      # Need to traverse the entire tree to update `seenP` and `seenQ`.
      left = getLCA(root.left, p, q)
      right = getLCA(root.right, p, q)
      if root == p:
        seenP = True
        return root
      if root == q:
        seenQ = True
        return root
      if left and right:
        return root
      return left or right

    lca = getLCA(root, p, q)
    return lca if seenP and seenQ else None

Approach 2: Standard LCA

  • Time: $O(n)$
  • Space: $O(h)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
 public:
  TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    TreeNode* ans = getLCA(root, p, q);
    if (ans == p)  // Search q in the subtree rooted at p.
      return getLCA(p, q, q) == nullptr ? nullptr : ans;
    if (ans == q)  // Search p in the subtree rooted at q.
      return getLCA(q, p, p) == nullptr ? nullptr : ans;
    return ans;  // (ans != p && ans != q) || ans == nullptr
  }

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
  public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    TreeNode ans = getLCA(root, p, q);
    if (ans == p) // Search q in the subtree rooted at p.
      return getLCA(p, q, q) == null ? null : ans;
    if (ans == q) // Search p in the subtree rooted at q.
      return getLCA(q, p, p) == null ? null : ans;
    return ans; // (ans != p && ans != q) || ans == null
  }

  private TreeNode getLCA(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q)
      return root;
    TreeNode left = getLCA(root.left, p, q);
    TreeNode right = getLCA(root.right, p, q);
    if (left != null && right != null)
      return root;
    return left == null ? right : left;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
  def lowestCommonAncestor(
      self,
      root: 'TreeNode',
      p: 'TreeNode',
      q: 'TreeNode',
  ) -> 'TreeNode':
    def getLCA(root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
      if not root or root == p or root == q:
        return root
      left = getLCA(root.left, p, q)
      right = getLCA(root.right, p, q)
      if left and right:
        return root
      return left or right

    ans = getLCA(root, p, q)
    if ans == p:  # Search q in the subtree rooted at p.
      return ans if getLCA(p, q, q) else None
    if ans == q:  # Search p in the subtree rooted at q.
      return ans if getLCA(q, p, p) else None
    return ans  # (ans != p and ans != q) or ans is None