LC 1123 [M] Lowest Common Ancestor of Deepest Leaves - ALawliet/algorithms GitHub Wiki

Solution 2: Get Subtree Deepest Depth
helper function return the deepest depth of descendants.
deepest represent the deepest depth.
We use a global variable lca to represent the result.
One pass, Time O(N) Space O(H)
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def lcaDeepestLeaves(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        self.lca = None
        self.max_depth = 0
        
        def postorder(node, d):
            self.max_depth = max(self.max_depth, d)
            
            if not node:
                return d
            
            L = postorder(node.left, d + 1)
            R = postorder(node.right, d + 1)
            
            if L == R == self.max_depth:
                self.lca = node
                
            return max(L, R)
        
        postorder(root, 0)
        return self.lca
Solution 1: Get Subtree Height and LCA
helper function return the lca, subtree height at the same time.
null node will return depth 0,
leaves will return depth 1.
class Solution2(object):
    def lcaDeepestLeaves(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        return self.postorder(root)[0]
        
    def postorder(self, root): # returns lca, subtree height
        if not root:
            return None, 0

        L, L_height = self.postorder(root.left)
        R, R_height = self.postorder(root.right)
        
        if L_height > R_height:
            return L, L_height + 1
        elif R_height > L_height:
            return R, R_height + 1
        else:
            return root, L_height + 1