""" 0543.1 - Diameter of Binary Tree - Solution 1 - DFS """
#####################################################################################
# Imports
#####################################################################################
from typing import Optional
#####################################################################################
# Classes
#####################################################################################
class TreeNode:
"""TreeNode Class"""
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
"""Solution Class"""
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
"""Diameter of Binary Tree Function"""
self.diameter = 0
def dfs(node: Optional[TreeNode]) -> int:
if not node:
return 0
left = dfs(node.left)
right = dfs(node.right)
self.diameter = max(self.diameter, left + right)
return 1 + max(left, right)
dfs(root)
return self.diameter
#####################################################################################
# Functions
#####################################################################################
def testcase():
"""Test Function"""
# Example 1: root = [1,2,3,4,5] -> Output: 3
root1 = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
print(Solution().diameterOfBinaryTree(root1)) # 3
# Example 2: root = [1,2] -> Output: 1
root2 = TreeNode(1, TreeNode(2))
print(Solution().diameterOfBinaryTree(root2)) # 1
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()
struct N{l:Option<Box<N>>,r:Option<Box<N>>}fn d(n:&Option<Box<N>>,a:&mut i32)->i32{if let Some(x)=n{let l=d(&x.l,a);let r=d(&x.r,a);*a=(*a).max(l+r);1+l.max(r)}else{0}}fn main(){let n=Some(Box::new(N{l:Some(Box::new(N{l:Some(Box::new(N{l:None,r:None})),r:Some(Box::new(N{l:None,r:None}))})),r:Some(Box::new(N{l:None,r:None}))}));let mut a=0;d(&n,&mut a);println!("{}",a)}
""" 0543.2 - Diameter of Binary Tree - Solution 2 - DFS with Tuple Return """
#####################################################################################
# Imports
#####################################################################################
from typing import Optional
#####################################################################################
# Classes
#####################################################################################
class TreeNode:
"""TreeNode Class"""
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
"""Solution Class"""
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
"""Diameter of Binary Tree Function"""
def dfs(node: Optional[TreeNode]) -> tuple:
if not node:
return (0, 0)
left_diameter, left_depth = dfs(node.left)
right_diameter, right_depth = dfs(node.right)
current_diameter = left_depth + right_depth
max_diameter = max(left_diameter, right_diameter, current_diameter)
max_depth = 1 + max(left_depth, right_depth)
return (max_diameter, max_depth)
diameter, _ = dfs(root)
return diameter
#####################################################################################
# Functions
#####################################################################################
def testcase():
"""Test Function"""
# Example 1: root = [1,2,3,4,5] -> Output: 3
root1 = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
print(Solution().diameterOfBinaryTree(root1)) # 3
# Example 2: root = [1,2] -> Output: 1
root2 = TreeNode(1, TreeNode(2))
print(Solution().diameterOfBinaryTree(root2)) # 1
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()
struct N{l:Option<Box<N>>,r:Option<Box<N>>}fn d(n:&Option<Box<N>>,a:&mut i32)->i32{if let Some(x)=n{let l=d(&x.l,a);let r=d(&x.r,a);*a=(*a).max(l+r);1+l.max(r)}else{0}}fn main(){let n=Some(Box::new(N{l:Some(Box::new(N{l:Some(Box::new(N{l:None,r:None})),r:Some(Box::new(N{l:None,r:None}))})),r:Some(Box::new(N{l:None,r:None}))}));let mut a=0;d(&n,&mut a);println!("{}",a)}
