Problem description

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Given the following binary tree: 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, q = 1 Output: 3 Explanation: The LCA of nodes 5 and 1 is 3. Example 2:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 Output: 5 Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Note:

All of the nodes’ values will be unique. p and q are different and both values will exist in the binary tree.

Solution

1. Notice this time, it is only binary tree (not binary search tree) so we need to check whether p and q are in the same subtree. If they both in left subtree, then recursive to left, if both are in right subtree recursive to right. Otherwise, return root.
2. We check quickly return if q is descendant of p or p is descendant of q.

Below is python implementation

# 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':
        
        def contains(root:'TreeNode', p:'TreeNode')->bool:
            if root == None:
                return False
            if p == root:
                return True
            return contains(root.left, p) or contains(root.right, p)
						
        if contains(p, q):
            return p
        if contains(q, p):
            return q
        if contains(root.left, p) and contains(root.left, q):
            return self.lowestCommonAncestor(root.left, p, q)
        elif contains(root.right, p) and contains(root.right, q):
            return self.lowestCommonAncestor(root.right, p, q)
        else:
            return root