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