Problem Statement
leetcode problem link
Brute Force [TLE]
# 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 diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
self.res = 0
def max_depth(node):
if not node:
return 0
L = max_depth(node.left) + 1
R = max_depth(node.right) + 1
return max(L, R)
def dfs(node):
if not node:
return 0
left = max_depth(node.left)
right = max_depth(node.right)
self.res = max(self.res, left + right)
dfs(node.left)
dfs(node.right)
return left + right - 2
dfs(root)
return self.res
Improved Approach [Accepted]
# 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 diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
self.res = 0
def dfs(node):
if not node:
return 0
left = dfs(node.left)
right = dfs(node.right)
self.res = max(self.res, left + right)
return max(left, right) + 1
dfs(root)
return self.res
Editorial
class Solution:
def diameterOfBinaryTree(self, root: TreeNode) -> int:
diameter = 0
def longest_path(node):
if not node:
return -1
nonlocal diameter
# recursively find the longest path in
# both left child and right child
left_path = longest_path(node.left)
right_path = longest_path(node.right)
# update the diameter if left_path plus right_path is larger
diameter = max(diameter, left_path + right_path + 2)
# return the longest one between left_path and right_path;
# remember to add 1 for the path connecting the node and its parent
return max(left_path, right_path) + 1
longest_path(root)
return diameter
