Diameter of Binary Tree
- 1 min read
- LC-Easy
- Binary Tree
3 years ago
Solution
- Similar to Binary Tree Diameter
- Also look at Height Balanced Binary Tree and Balanced Binary Tree
- Basically, we're just going to use a helper function to recur down the tree and calculate the heights of the left and right subtrees.
- Since there would be repeated work, we kinda work our way to the leaf nodes and recur up.
- Whenever we're doing this, we just use the left and height subtree heights from a given node to update a global variable which contains the length of the longest path in the tree.
| Time | Space | Explanation |
|---|---|---|
O(n) | O(h) | Typical binary tree complexities |
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
ans = 0
def helper(node):
if node is None:
return 0
nonlocal ans
left = helper(node.left)
right = helper(node.right)
ans = max(ans, left + right)
return 1 + max(left, right)
helper(root)
return ans