LC 0865 [M] Smallest Subtree with all the Deepest Nodes - ALawliet/algorithms GitHub Wiki
trick is to calculate the height from the bottom up
/**
* The question is unclear. For example, if we did not have nodes 7 and 4, the answer would
* be TreeNode(3). If we did not have node 4, the answer would be TreeNode(7) and not
* TreeNode(2). Similarly, if we did not have 7, the answer would be TreeNode(4) and not
* TreeNode(2).
*
* Intuitively, we should be traversing from the children to the parent and calculate the
* height from bottom. So the null nodes would have height 0. The leaf nodes would have the
* height 1 and the root would have the max height.
* At each node, we keep a pair<height_of_node_from_bottom, node>. At a given node, if we
* realize that the leftHeight == rightHeight, it means we have found the deepest subtree
* rooted at node. If leftHeight > rightHeight, it means the deepest subtree must be rooted
* at left child. If rightHeight > leftHeight, it means the deepest subtree must be rooted
* at right child.
* Which traversal allows us to traverse from bottom-up? Postorder! So we use it in the code.
*/
# 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 subtreeWithAllDeepest(self, root):
# return (height, parent)
def height(node):
if not node:
return (0, None)
l = height(node.left)
r = height(node.right)
if l[0] == r[0]:
return (l[0] + 1, node) # can return (l[0] or r[0] + 1, ancestor)
elif l[0] > r[0]:
return (l[0] + 1, l[1])
elif l[0] < r[0]:
return (r[0] + 1, r[1])
return height(root)[1]