Diameter of Binary Tree - LeetCode
Given the root of a binary tree, return the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root. The length of a path between two nodes is represented by the number of edges between them.
Example 1:
Input: root = [1,2,3,4,5] Output: 3 Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].
Example 2:
Input: root = [1,2] Output: 1
Constraints:
The number of nodes in the tree is in the range [1, 104].
-100 <= Node.val <= 100
- code
class Solution:
def dfs(self, node):
if not node: return 0
left = 1 + self.dfs(node.left)
right = 1 + self.dfs(node.right)
return max(left, right)
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
curDia = leftDia = rightDia = 0
if root.left:
leftDia = self.diameterOfBinaryTree(root.left)
if root.right:
rightDia = self.diameterOfBinaryTree(root.right)
leftDepth = self.dfs(root.left)
rightDepth = self.dfs(root.right)
curDia = leftDepth + rightDepth
return max(leftDia, rightDia, curDia)
- code
class Solution:
def diameterOfBinaryTree(self, root: TreeNode) -> int:
self.diameter = 0
def longest_path(node):
if not node:
return 0
left_path = longest_path(node.left)
right_path = longest_path(node.right)
self.diameter = max(self.diameter, left_path + right_path)
return max(left_path, right_path) + 1
longest_path(root)
return self.diameter
- code
class Solution:
def dfs(self, node):
if not node: return 0
left = self.dfs(node.left)
right = self.dfs(node.right)
self.diameter = max(self.diameter, left + right)
return max(left, right) + 1
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
self.diameter = 0
self.dfs(root)
return self.diameter