Algorithm
Problem Name: 543. Diameter of Binary Tree
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
Code Examples
#1 Code Example with C Programming
Code -
C Programming
int depth(struct TreeNode *node, int *m) {
int l, r;
if (!node) return 0;
l = depth(node->left, m);
r = depth(node->right, m);
if (*m < l + r) *m = l + r;
if (r < l) r = l;
return r + 1;
}
int diameterOfBinaryTree(struct TreeNode* root) {
int m = 0;
depth(root, &m);
return m;
}
Input
Output
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
int diameterOfBinaryTree(TreeNode* root) {
int maxLen = 0;
DFS(root, maxLen);
return maxLen;
}
private:
int DFS(TreeNode* root, int& maxLen){
if(!root) return 0;
int left = DFS(root->left, maxLen);
int right = DFS(root->right, maxLen);
maxLen = max(maxLen, left + right);
return max(left, right) + 1;
}
};
Input
Output
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int diameterOfBinaryTree(TreeNode root) {
int[] diameter = {0};
dfs(root, diameter);
return diameter[0];
}
private int dfs(TreeNode root, int[] diameter) {
if (root == null) {
return 0;
}
int leftDiameter = dfs(root.left, diameter);
int rightDiameter = dfs(root.right, diameter);
diameter[0] = Math.max(leftDiameter + rightDiameter, diameter[0]);
return Math.max(leftDiameter, rightDiameter) + 1;
}
}
Input
Output
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const diameterOfBinaryTree = function (root) {
if (root === null) return 0
let longest = 0
function dfs(node) {
if (node === null) return 0
let leftmax = dfs(node.left)
let rightmax = dfs(node.right)
longest = Math.max(longest, leftmax + 1 + rightmax)
return Math.max(leftmax, rightmax) + 1
}
dfs(root)
return longest - 1
}
Input
Output
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def diameterOfBinaryTree(self, root):
"""
:type root: TreeNode
:rtype: int
"""
res = [0]
def traverse(node):
if not node: return 0
left, right = traverse(node.left), traverse(node.right)
res[0] = max(left+right, res[0])
return 1+ max(left, right)
traverse(root)
return res[0]
Input
Output
#6 Code Example with C# Programming
Code -
C# Programming
using System;
namespace LeetCode
{
public class _0543_DiameterOfBinaryTree
{
private int answer;
public int DiameterOfBinaryTree(TreeNode root)
{
GetEdgeDepth(root);
return answer;
}
private int GetEdgeDepth(TreeNode root)
{
if (root == null) return 0;
var left = GetEdgeDepth(root.left);
var right = GetEdgeDepth(root.right);
this.answer = Math.Max(this.answer, left + right);
return Math.Max(left, right) + 1;
}
}
}
Input
Output