1123. LCA of Deepest Leaves

Loading...LeetCode

题目要求 deepest leaves 的LCA，而不是所有leaves的LCA（which is the root），其实就是说，左右子节点高度不一致的话，只考虑高度较高那个（leaf较深）；高度一致，则说明当前节点就是其 deepest leaves LCA。根据这个原则往上递归，返回根节点获得的deepest leaves LCA即可。

看到有拿memo记录的解法，其实这题没什么重复运算，每个node肯定只被搜索一次，不需要memo...

Python

# 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: TreeNode) -> TreeNode:
        def postorder(root):
            if not root: return (0, None)
            d_l, lca_l = postorder(root.left)
            d_r, lca_r = postorder(root.right)
            if d_l == d_r: # same height => both are deepest, a tie
                return (d_l+1, root)
            if d_l > d_r: # right leaf is deeper than left
                return (d_l+1, lca_l)
            else:
                return (d_r+1, lca_r)
        return postorder(root)[1]