The last common ancestor of the leetcode_236 binary tree

requirements

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 as follows: “For two nodes P and Q with root tree T, the nearest common ancestor is expressed as a node X, which satisfies that X is the ancestor of P and Q and the depth of X is as large as possible (a node can also be its own ancestor).

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.Copy the code

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.Copy the code

Example 3:

Input: root = [1,2], P = 1, q = 2 Output: 1Copy the code

The core code

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 not root or root == p or root == q:
            return root
        else:
            left = self.lowestCommonAncestor(root.left,p,q)
            right = self.lowestCommonAncestor(root.right,p,q)

            if left and right:
                return root
            elif left:
                return left
            elif right:
                return right
            else:
                return 
Copy the code

If the current node is P or Q, it indicates that the current node is the nearest ancestor. If the current node is not p or P, try to find pQ in the left and right subtrees. If pQ is found in one left and one right, then the current node is still the closest ancestor of root. Otherwise, return the side where they are both.