Dare2Solve
The diameter of a binary tree is defined as the length of the longest path between any two nodes in the tree. This path may or may not pass through the root. The goal is to compute the diameter of a given binary tree.
The diameter of a binary tree can be determined by finding the longest path that goes through each node and keeping track of the maximum of these paths. For each node, this longest path can be calculated by the sum of the heights of its left and right subtrees.
maxDiameter
to keep track of the maximum diameter encountered.dfs
that returns the height of a node.dfs
function:
null
, return 0.dfs
for the left and right children to get their heights.maxDiameter
with the maximum value of the sum of the left and right heights.dfs
function with the root node.maxDiameter
.O(n), where n is the number of nodes in the tree. Each node is visited once.
O(h), where h is the height of the tree. This space is used by the recursion stack.
class Solution {
public:
int diameterOfBinaryTree(TreeNode* root) {
int maxDiameter = 0;
std::function<int(TreeNode*)> dfs = [&](TreeNode* node) {
if (!node) return 0;
int left = dfs(node->left);
int right = dfs(node->right);
maxDiameter = std::max(maxDiameter, left + right);
return std::max(left, right) + 1;
};
dfs(root);
return maxDiameter;
}
};
class Solution:
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
self.max_diameter = 0
def dfs(node):
if not node:
return 0
left_height = dfs(node.left)
right_height = dfs(node.right)
# Update the diameter if the path through the current node is larger
self.max_diameter = max(self.max_diameter, left_height + right_height)
# Return the height of the tree
return max(left_height, right_height) + 1
dfs(root)
return self.max_diameter
class Solution {
private int maxDiameter = 0;
public int diameterOfBinaryTree(TreeNode root) {
dfs(root);
return maxDiameter;
}
private int dfs(TreeNode node) {
if (node == null) return 0;
int left = dfs(node.left);
int right = dfs(node.right);
maxDiameter = Math.max(maxDiameter, left + right);
return Math.max(left, right) + 1;
}
}
var diameterOfBinaryTree = function(root) {
let max = 0
function dfs(node) {
if (!node) return 0
const left = dfs(node.left)
const right = dfs(node.right)
console.log(node.val, left, right)
max = Math.max(max, left + right)
return Math.max(left, right) + 1
}
dfs(root)
return max
};