leetcode

Leetcode submissions
git clone git://git.laack.co/leetcode.git
Log | Files | Refs | README

diameter-binary-tree.py (1113B)

      1 # Definition for a binary tree node.
      2 # class TreeNode:
      3 #     def __init__(self, val=0, left=None, right=None):
      4 #         self.val = val
      5 #         self.left = left
      6 #         self.right = right
      7 
      8 #         addl : right_height
      9 #         addl : left_height
     10 
     11 # Idea:
     12 
     13 # Find height of left and right at each node.
     14 # Return this up the stack. Incrementing longest as we return.
     15 
     16 # for each element, we then sum left and right heights and return largest one.
     17 
     18 
     19 class Solution:
     20     def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
     21 
     22         if root.left is None and root.right is None:
     23             return 0
     24 
     25         return get_heights(root)[1]
     26 
     27 
     28 # TUPLE:
     29 # [0] is the number of traversals to the bottom
     30 # [1] is the max traversals in the tree
     31 
     32 
     33 def get_heights(node: TreeNode):
     34     if node is None:
     35         return [-1, 0]
     36 
     37     left_tuple = get_heights(node.left)
     38     right_tuple = get_heights(node.right)
     39 
     40     lh = left_tuple[0] + 1
     41     rh = right_tuple[0] + 1
     42 
     43     node.left_height = lh
     44     node.right_height = rh
     45 
     46     current = lh + rh
     47 
     48     return max(lh, rh), max(current, left_tuple[1], right_tuple[1])