adamgarcia4 · July 27, 2020 21:31
diff --git a/LCA Code b/LCA 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':
        '''
        Two takeaways:
        Takeaway 1
            Build solution by starting with trivial case.
            Then add a little bit more (1 more element).
            Continue growing and considering all cases until we reach a subproblem.
            
        Takeaway 2
            Really understand what the invariant (LCA) is.
            LCA Def'n
                LCA of a Null node is undefined.
                LCA where one element is the root
                    The root is by def'n the LCA.
                LCA where p and q are in DIFFERENT subtrees is the root.
                LCA will be found in EITHER the left or the right.
        '''
        # In an empty binary tree, there are no common ancestors.
        if root is None:
            return None

        # After the first Base Case, root cannot be None.
        
        # Root is EITHER p or q.
        if root is p or root is q:
            # This is the LCA because It is both p or q, AND the LCA.
            return root
        
        # root is NOT p AND NOT q.
        # LCA is definitely going to be entirely in the left or right subtree.
        left_lca = self.lowestCommonAncestor(root.left, p, q)
        right_lca = self.lowestCommonAncestor(root.right, p, q)
        
        # Case where p and q are found in different subtrees
        # Therefore, the root is the LCA
        if left_lca and right_lca:
            return root
        
        # p and q are both in the same subtree, therefore, the LCA is defined
        # only on the left or only on the right
        if not left_lca:
            return right_lca
        return left_lca
	# 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':
	'''
	Two takeaways:
	Takeaway 1
	Build solution by starting with trivial case.
	Then add a little bit more (1 more element).
	Continue growing and considering all cases until we reach a subproblem.

	Takeaway 2
	Really understand what the invariant (LCA) is.
	LCA Def'n
	LCA of a Null node is undefined.
	LCA where one element is the root
	The root is by def'n the LCA.
	LCA where p and q are in DIFFERENT subtrees is the root.
	LCA will be found in EITHER the left or the right.
	'''
	# In an empty binary tree, there are no common ancestors.
	if root is None:
	return None

	# After the first Base Case, root cannot be None.

	# Root is EITHER p or q.
	if root is p or root is q:
	# This is the LCA because It is both p or q, AND the LCA.
	return root

	# root is NOT p AND NOT q.
	# LCA is definitely going to be entirely in the left or right subtree.
	left_lca = self.lowestCommonAncestor(root.left, p, q)
	right_lca = self.lowestCommonAncestor(root.right, p, q)

	# Case where p and q are found in different subtrees
	# Therefore, the root is the LCA
	if left_lca and right_lca:
	return root

	# p and q are both in the same subtree, therefore, the LCA is defined
	# only on the left or only on the right
	if not left_lca:
	return right_lca
	return left_lca