30min
class Solution2:
def __init__(self):
self.res=None
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
self.dfs(root,p,q)
return self.res
def dfs(self,root:TreeNode,p:TreeNode,q:TreeNode)->bool:
if not root:return False
left=1 if self.dfs(root.left,p,q) else 0
right=1 if self.dfs(root.right,p,q) else 0
mid=1 if root==p or root==q else 0
if left+right+mid>1:self.res=root
return left or right or mid # 这里要有mid
有问题的写法,函数功能写得很乱
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if not root: return None
if self.subTreeHasNode(root,p,q):return root
left=self.lowestCommonAncestor(root.left,p,q)
if left:return left
right=self.lowestCommonAncestor(root.right,p,q)
if right:return right
def subTreeHasNode(self,root:TreeNode,p:TreeNode,q:TreeNode)->bool:
if not root:return True
mid=True if root==p or root==q else False
left=self.subTreeHasNode(root.left,p,q)
right=self.subTreeHasNode(root.right,p,q)
if (mid and left)or (mid and right)or(left and right):return True #到底是含有一个节点?还是两边都有呢?
网友评论