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
My Solution
We can solve this problem by first finding the depths of all the nodes in the tree. Then the diameter from every node is the sum of the depth of the left subtree and the depth of the right subtree. We visit all the nodes in the tree and keep track of the maximum diameter, which we return in the end. We also use a HashMap to store the depth of every node.
Time complexity is O(n), where n is the number of elements in the tree because we visit every node twice. Space complexity is also O(n) to store the depths of every node.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int diameterOfBinaryTree(TreeNode root) {
Map<TreeNode,Integer> depths = new HashMap<>();
depth(root, depths);
return diameter(root, depths);
}
public int depth(TreeNode root, Map<TreeNode,Integer> depths) {
int depth = 0;
if (root.left != null) {
depth = 1 + depth(root.left, depths);
}
if (root.right != null) {
depth = Math.max(depth, 1 + depth(root.right, depths));
}
depths.put(root, depth);
return depth;
}
public int diameter(TreeNode root, Map<TreeNode,Integer> depths) {
if (root == null) {
return 0;
}
int out = 0;
if (root.left != null) {
out += 1 + depths.get(root.left);
}
if (root.right != null) {
out += 1 + depths.get(root.right);
}
out = Math.max(out, diameter(root.left, depths));
out = Math.max(out, diameter(root.right, depths));
return out;
}
}