Sponsored
Sponsored
This approach uses a depth-first search (DFS) to calculate the diameter of the binary tree. The key idea is to determine the longest path passing through each node and update the maximum diameter accordingly.
By computing the height of the left and right subtrees at each node, we can obtain the potential diameter passing through that node as the sum of the heights plus one. We will keep track of the global diameter, updating it as necessary.
Time Complexity: O(N), where N is the number of nodes. Each node is visited once.
Space Complexity: O(H), where H is the height of the tree, representing the call stack size due to recursion.
1#include <stdio.h>
2#define max(a,b) ((a)>(b)?(a):(b))
3
4struct TreeNode {
5 int val;
6 struct TreeNode *left;
7 struct TreeNode *right;
8};
9
10int diameter = 0;
11
12int dfs(struct TreeNode* root) {
13 if (!root) return 0;
14 int left = dfs(root->left);
15 int right = dfs(root->right);
16 diameter = max(diameter, left + right);
17 return max(left, right) + 1;
18}
19
20int diameterOfBinaryTree(struct TreeNode* root) {
21 diameter = 0;
22 dfs(root);
23 return diameter;
24}The implementation involves a helper function dfs that traverses the tree recursively. For each node, it calculates the height of the left and right subtrees. The diameter is updated as the maximum of the current diameter and the sum of the heights of the left and right subtrees. The function diameterOfBinaryTree initializes the diameter and invokes the DFS.
This method enhances the recursive DFS approach by incorporating memoization for subtree height calculations, thereby eliminating redundant computations and improving performance, especially beneficial for trees with high duplication of node structures.
Time Complexity: Approaches O(N) due to controlled redundant calculations via memoization.
Space Complexity: O(N) for storing the heights in the memo array.
1
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
this.val = val;
this.left = left;
this.right = right;
}
}
public class Solution {
private int diameter = 0;
private Dictionary<TreeNode, int> memo = new Dictionary<TreeNode, int>();
private int DFS(TreeNode node) {
if (node == null) return 0;
if (memo.ContainsKey(node)) return memo[node];
int left = DFS(node.left);
int right = DFS(node.right);
diameter = Math.Max(diameter, left + right);
int height = Math.Max(left, right) + 1;
memo[node] = height;
return height;
}
public int DiameterOfBinaryTree(TreeNode root) {
DFS(root);
return diameter;
}
}C# leverages a Dictionary for storing the heights of nodes as they are calculated, thus vastly improving the recursive DFS function by reusing already calculated data.