0543. Diameter of Binary Tree
https://leetcode.com/problems/diameter-of-binary-tree
Description
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
ac
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private int diameter = 0;
public int diameterOfBinaryTree(TreeNode root) {
max(root);
return diameter;
}
private int max(TreeNode root) {
// exit
if (root == null) return 0;
// divide and conquer
int lmax = max(root.left);
int rmax = max(root.right);
diameter = Math.max(diameter, lmax + rmax);
return Math.max(lmax+1, rmax+1);
}
}
Last updated
Was this helpful?