Within in the first 3 minutes of your video I figured out why my code wasn't working. Once I did a check for P and for Q separately first to confirm they both exist, my solution started working. All I had to do is check if P or Q doesn't exist and return Null, if they both exist, then I can do the normal "find ancestor" code. But of course this wasn't efficient enough, so thank you for showing me the optimized version
Yes. This is the same question I have. Also if P and Q both are found in left subtree, why do we have to still traverse right subtree? That does not seem necessary.
how l or r works was something new to me # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def lowestCommonAncestor(self, root, p, q): """ :type root: TreeNode :type p: TreeNode :type q: TreeNode :rtype: TreeNode """ self.p_found = False self.q_found = False ans = self.helper(root, p, q) return ans if self.p_found and self.q_found else None def helper(self, node, p, q): if not node: return None l = self.helper(node.left, p, q) r = self.helper(node.right, p, q) if node == p: self.p_found = True return node if node == q: self.q_found = True return node if l and r: return node else: return l or r
Thank you so much brotha! may GOD bless you with more TC from meta!!!
Wow, the explanation was super clear! Thx, mate!
Thanks! Make sure to subscribe if you haven’t already 😉
Within in the first 3 minutes of your video I figured out why my code wasn't working. Once I did a check for P and for Q separately first to confirm they both exist, my solution started working.
All I had to do is check if P or Q doesn't exist and return Null, if they both exist, then I can do the normal "find ancestor" code.
But of course this wasn't efficient enough, so thank you for showing me the optimized version
8:59 sorry I am confused here. If returning 4 or 5 doesn't matter, how would the algorithm make sure to return the correct answer, 5 but not 4?
Yes. This is the same question I have. Also if P and Q both are found in left subtree, why do we have to still traverse right subtree? That does not seem necessary.
Thank you . Your channel videos are super easy to understand.
how l or r works was something new to me
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def lowestCommonAncestor(self, root, p, q):
"""
:type root: TreeNode
:type p: TreeNode
:type q: TreeNode
:rtype: TreeNode
"""
self.p_found = False
self.q_found = False
ans = self.helper(root, p, q)
return ans if self.p_found and self.q_found else None
def helper(self, node, p, q):
if not node:
return None
l = self.helper(node.left, p, q)
r = self.helper(node.right, p, q)
if node == p:
self.p_found = True
return node
if node == q:
self.q_found = True
return node
if l and r:
return node
else:
return l or r
Great Explanation! Thanks!
Glad you enjoyed the video! Make sure to subscribe so you don’t miss future videos
Thank you for explaining, it was helpful!
Glad you found the video helpful! Make sure to subscribe so you don’t miss other videos coming soon
Wouldn't storing l and r result in an O(N) space complexity? Since the None value also takes space in memory as well.