Topic describes

Given a binary tree, find the nearest common ancestor of the two specified nodes in the tree.

The definition of the nearest common ancestor in Baidu encyclopedia is: “For the two nodes P and Q with root tree T, the nearest common ancestor is expressed as a node X, satisfying that X is the ancestor of P and Q and x is as deep as possible (a node can also be its own ancestor).

For example, a given binary tree as follows: root = [3,5,1,6,2,0,8, null, null, 7, 4]

Example 1: input: root = [3,5,1,6,2,0,8, null, null, 7, 4], p = 5, output q = 1:3: node 5 and 1 recent common ancestor node 3.

Example 2: input: root = [3,5,1,6,2,0,8, null, null, 7, 4], p = 5, q = 4 output: 5: node 5 nodes and four recent common ancestor is 5. Because by definition the nearest common ancestor node can be the node itself.

Their thinking

  1. Unlike 68-1, this problem is not a binary sorting tree, so we cannot determine the ancestor node from size alone; So we use recursive processing
  2. Directly recurse the left and right nodes of the root node to determine whether the child nodes are the same as P and q. If so, return; If they’re different, they keep recursing to nil
  3. When we recurse to child nodes, we get left and right, and their values could be P, q, or nil. If left is nil, return right; If right is nil, return left; If none of them are nil, we return root, and root has a common ancestor, and we return root up

The sample code

def lowestCommonAncestor(
    self, root: TreeNode, p: TreeNode, q: TreeNode
) -> TreeNode:
    if not root or root == p or root == q:
        return root
    left = self.lowestCommonAncestor(root.left, p, q)
    right = self.lowestCommonAncestor(root.right, p, q)
    if not left:
        return right
    if not right:
        return left
    return root
Copy the code