Lc236. The most recent common ancestor of binary trees

Title description:

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).

参 考 答 案 :

L = helper(root.left,p,q) : L = helper(root.left,p,q) : L = helper(root.left,p,q) : L = helper(root.left,p,q) : R = Helper (root.right,p,q) : helper(root.right,p,q) : Helper (root

If L and R are true, the most recent common ancestor is root

Either L or R is true and its parent is root==p or root==q, indicating that the most recent common ancestor is root

Reference code

# 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':
        self.ans = root
        self.helper(root,p,q)
        return self.ans
    def helper(self,root,p,q):
        if root is None:
            return False
        L = self.helper(root.left,p,q)
        R = self.helper(root.right,p,q)
        if L and R:
            self.ans = root
        if ( L or R ) and (root == p or root == q):
            self.ans = root
        return L or R or p == root or q == root
Copy the code