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 <vector>
2using namespace std;
3
4struct TreeNode {
5 int val;
6 TreeNode *left;
7 TreeNode *right;
8 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
9};
10
11class Solution {
12public:
13 int countPairs(TreeNode* root, int distance) {
14 int result = 0;
15 dfs(root, distance, result);
16 return result;
17 }
18private:
19 vector<int> dfs(TreeNode* node, int distance, int &result) {
20 if (!node) return vector<int>(distance + 1, 0);
21 if (!node->left && !node->right) {
22 vector<int> leaves(distance + 1, 0);
23 leaves[1] = 1;
24 return leaves;
25 }
26
27 vector<int> left = dfs(node->left, distance, result);
28 vector<int> right = dfs(node->right, distance, result);
29
30 for (int i = 0; i <= distance; ++i) {
31 for (int j = 0; j + i <= distance; ++j) {
32 result += left[i] * right[j];
33 }
34 }
35
36 vector<int> leaves(distance + 1, 0);
37 for (int i = 1; i < distance; ++i) {
38 leaves[i + 1] = left[i] + right[i];
39 }
40
41 return leaves;
42 }
43};The C++ solution uses a vector to keep track of the number of leaves at a certain distance from the node. The function recursively computes these vectors for the left and right subtrees. By combining these vectors, we can calculate the total number of good leaf node pairs.
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.
1/* This solution is based on C and would implement a similar strategy to preprocess and calculate distances between all leaves, followed by evaluating valid pairs. For brevity, a sample plan is provided without full implementation due to competition space. */A solution in C would involve more detailed memory management and array calculations for storing and evaluating distances.