LeetCode 236. [Python] Lowest Common Ancestor of a Binary Tree
原题链接
中等
作者:
徐辰潇
,
2021-01-13 00:07:28
,
所有人可见
,
阅读 367
# 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':
#TC: O(total nodes)
#SC: O(maximum depth)
#There are two situations
# 1. p is a ancestor of q (or the reverse)
# 2. p is not a an ancestor of q, i.e. they share a common ancestor
def help(Node):
#In this case, we met the leaf node, just return none
if not Node:
return
#If we found p or q, just return the node
if Node.val == p.val or Node.val == q.val:
return Node
left = help(Node.left)
right = help(Node.right)
#This corresponding to situation 2
#If the groundtruth is situation 1, then the p and q is passed to the first layer
if left and right:
return Node
if left:
return left
if right:
return right
return None
return help(root)