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.
1class TreeNode:
2 def __init__(self, val=0, left=None, right=None):
3 self.val = val
4 self.left = left
5 self.right = right
6
7class Solution:
8 def diameterOfBinaryTree(self, root: TreeNode) -> int:
9 self.diameter = 0
10 def dfs(node):
11 if not node:
12 return 0
13 left = dfs(node.left)
14 right = dfs(node.right)
15 self.diameter = max(self.diameter, left + right)
16 return max(left, right) + 1
17 dfs(root)
18 return self.diameterThe Python solution involves a class variable diameter to store the longest path found. The dfs function recursively finds the height of each subtree and adjusts the diameter with potential candidates. The main function diameterOfBinaryTree initializes the process.
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#include <algorithm>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
vector<int> memo;
int diameter;
int dfs(TreeNode* root, int node_idx) {
if (!root) return 0;
if (memo[node_idx] != -1) return memo[node_idx];
int left = dfs(root->left, node_idx * 2 + 1);
int right = dfs(root->right, node_idx * 2 + 2);
diameter = max(diameter, left + right);
memo[node_idx] = max(left, right) + 1;
return memo[node_idx];
}
int diameterOfBinaryTree(TreeNode* root) {
if (!root) return 0;
memo.assign(10000, -1);
diameter = 0;
dfs(root, 0);
return diameter;
}
};C++ introduces an auxiliary vector memo to help memoize heights of subtrees to prevent repetitive recalculative operations, especially effective in uniformly structured trees.