LC 0543 [E] Diameter of Binary Tree - ALawliet/algorithms GitHub Wiki
the diameter is the longest path between any 2 nodes. it is a classic post-order problem because we need to go down the L and R subtrees to calculate the heights before we can get the diameter
- inverted-V where the final diameter is the max of the / and \ height paths
- global problem: max diameter
- local problem: max height
class Solution:
def diameterOfBinaryTree(self, root: TreeNode) -> int:
self.max_diameter = 0
def postorder(x):
if not x: return 0
L = postorder(x.left)
R = postorder(x.right)
diameter = L + R
self.max_diameter = max(self.max_diameter, diameter)
return max(L, R) + 1 # choose bigger path + 1 for current
postorder(root)
return self.max_diameter
class Solution:
def diameterOfBinaryTree(self, root: TreeNode) -> int:
def dfs(node):
if not node.left and not node.right:
return 0
L_h = R_h = 0
diameter = 0
if node.left:
L_h = dfs(node.left)
diameter += L_h + 1
if node.right:
R_h = dfs(node.right)
diameter += R_h + 1
self.Diameter = max(self.Diameter, diameter)
h = max(L_h, R_h) + 1
return h
if not root: return 0
self.Diameter = 0
dfs(root)
return self.Diameter
class TreeDiameter:
def find_diameter(self, root):
self.Diameter = 0
self.h(root)
return self.Diameter
def h(self, node):
if node is None: return 0
L_h = self.h(node.left)
R_h = self.h(node.right)
# diameter at the current node will be equal to
# the height of left subtree + the height of right sub-trees + '1' for the current node
diameter = L_h + R_h + 1
# update the global tree diameter
self.Diameter = max(self.Diameter, diameter)
# height of the current node will be equal to
# the maximum of the height of left or right subtrees plus '1' for the current node
return max(L_h, R_h) + 1