543. Diameter of Binary Tree
Description
Given a binary tree, you need to compute 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.
Constraints
Approach
Links
GeeksforGeeks
ProgramCreek
Examples
Input: [1, 2, 3, 4, 5, null, null, 6, null, null, null, 7]
Output: 5
Input: []
Output: 0
Input: [1]
Output: 0
Input: [1, 2, 3, 4, 5, 6, 7]
Output: 4
Solutions
// 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;
}
}/**
* Time complexity :
* Space complexity :
*/
class Solution {
private int diameter = 0;
public int diameterOfBinaryTree(TreeNode root) {
getDiameter(root);
return diameter;
}
private int getDiameter(TreeNode node) {
if(node == null) {
return 0;
}
int lh = getDiameter(node.left);
int rh = getDiameter(node.right);
diameter = Math.max(diameter, lh+rh);
return 1 + Math.max(lh, rh);
}
}Follow up
Last updated
Was this helpful?