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
The length of a path between two nodes is represented by the number of edges between them.
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].
Input: root = [1,2] Output: 1
- The number of nodes in the tree is in the range
-100 <= Node.val <= 100
In this problem we are asked to find the length of the longest path between two nodes in a binary tree. Since we can only traverse a binary tree from top to bottom, we know that the answer to this problem will include some sort of tree traversal.
If we draw out an example tree, we can see that the longest possible path in a binary tree will start at one leaf node, pass through a lowest common ancestor, and then terminate at another leaf node. In the diagram below, we can see that the longest path in the binary tree passes through node
2. If we know the max height of the
right subtrees, we can calculate the maximum path length.
Since we need to know the max height of the
right subtrees for each node we visit, we will need to use a post-order traversal to solve this problem. We can base our solution on Leetcode 104: Maximum Depth of Binary Tree. Only in our case, we will add some logic to compare the longest path at each node to the global max path.
# 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: """ T: O(N) S: O(N) ~ worst; O(log N) ~ perfectly balanced This solution is based on: https://jessechaulk.com/posts/104-maximum-depth-of-binary-tree/ """ self.ans = 0 def helper(node): if not node: return 0 # Find the max height of the left and right subtrees left = helper(node.left) right = helper(node.right) # Check the sum of the left + right subtrees and update the # longest path variable if applicable. self.ans = max(self.ans, left + right) # Return the height of the max of the left and right subtrees. # Add 1 to the result to account for the height of the current # node return max(left, right) + 1 helper(root) return self.ans