Sponsored
Sponsored
This approach involves a DFS traversal of the tree. For each node, we compute the number of leaf nodes at each possible distance. We merge the results from the left and right subtrees and count the valid leaf pairs.
Time Complexity: O(n * distance) due to traversing the entire tree and computing leaf pairs.
Space Complexity: O(distance) for storing distance arrays.
1#include <stdio.h>
2#include <stdlib.h>
3#define MAX_DIST 10
4
5typedef struct TreeNode {
6 int val;
7 struct TreeNode *left;
8 struct TreeNode *right;
9} TreeNode;
10
11int distanceArray[MAX_DIST + 1];
12
13int dfs(TreeNode* node, int distance, int* result) {
14 if (!node) return NULL;
15 int leftDistances[MAX_DIST + 1] = {0};
16 int rightDistances[MAX_DIST + 1] = {0};
17
18 if (!node->left && !node->right) {
19 distanceArray[0] = 1;
20 return 1;
21 }
22
23 if (node->left) {
24 dfs(node->left, distance, result);
25 for (int i = 0; i < MAX_DIST; ++i) {
26 leftDistances[i + 1] = distanceArray[i];
27 }
28 }
29 if (node->right) {
30 dfs(node->right, distance, result);
31 for (int i = 0; i < MAX_DIST; ++i) {
32 rightDistances[i + 1] = distanceArray[i];
33 }
34 }
35
36 for (int i = 0; i <= distance; ++i) {
37 for (int j = 0; j + i <= distance; ++j) {
38 *result += leftDistances[i] * rightDistances[j];
39 }
40 }
41
42 for (int i = 0; i <= distance; ++i) {
43 distanceArray[i] = leftDistances[i] + rightDistances[i];
44 }
45
46 return 1;
47}
48
49int countPairs(TreeNode* root, int distance) {
50 int result = 0;
51 dfs(root, distance, &result);
52 return result;
53}In this C implementation of the DFS approach, we maintain arrays to count leaf nodes at particular distances for each subtree. We combine these left and right arrays for each node and calculate valid pairs within the distance constraint. The result is accumulated during the traversal.
This approach leverages preprocessing leaf distances in a dynamic programming table, which gives quick lookups during pair evaluation. It builds the DP table during a DFS traversal, allowing efficient pair computation afterward.
Time Complexity: Approximately O(n^2) for thorough pairing and evaluation.
Space Complexity: O(n^2) due to pair-wise distance visualization.
1class Solution {
2In Java, leveraging collections like List or Map can facilitate the handling of distance calculations and correlate these towards optimized leaf pair determination.