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