Question

04.08. First Common Ancestor

中文文档

Description

Design an algorithm and write code to find the first common ancestor of two nodes in a binary tree. Avoid storing additional nodes in a data structure. NOTE: This is not necessarily a binary search tree.

For example, Given the following tree: root = [3,5,1,6,2,0,8,null,null,7,4]

  3

   / \

  5   1

 / \ / \

6  2 0  8

  / \

 7   4

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1

Input: 3

Explanation: The first common ancestor of node 5 and node 1 is node 3.

Example 2:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4

Output: 5

Explanation: The first common ancestor of node 5 and node 4 is node 5.

Notes:

• All node values are pairwise distinct.
• p, q are different node and both can be found in the given tree.

Solutions

Solution 1

# Definition for a binary tree node.
# class TreeNode:
#   def __init__(self, x):
#     self.val = x
#     self.left = None
#     self.right = None


class Solution:
  def lowestCommonAncestor(
    self, root: TreeNode, p: TreeNode, q: TreeNode
  ) -> TreeNode:
    if root is None or root == p or root == q:
      return root
    left = self.lowestCommonAncestor(root.left, p, q)
    right = self.lowestCommonAncestor(root.right, p, q)
    return right if left is None else (left if right is None else root)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *   int val;
 *   TreeNode left;
 *   TreeNode right;
 *   TreeNode(int x) { val = x; }
 * }
 */
class Solution {
  public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) {
      return root;
    }
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    return left == null ? right : (right == null ? left : root);
  }
}