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.
1class TreeNode {
2 int val;
3 TreeNode left;
4 TreeNode right;
5 TreeNode(int x) { val = x; }
6}
7
8class Solution {
9 public int countPairs(TreeNode root, int distance) {
10 int[] result = new int[1];
11 dfs(root, distance, result);
12 return result[0];
13 }
14
15 private int[] dfs(TreeNode node, int distance, int[] result) {
16 if (node == null) return new int[distance + 1];
17 if (node.left == null && node.right == null) {
18 int[] leaves = new int[distance + 1];
19 leaves[1] = 1;
20 return leaves;
21 }
22
23 int[] left = dfs(node.left, distance, result);
24 int[] right = dfs(node.right, distance, result);
25
26 for (int i = 1; i <= distance; i++) {
27 for (int j = 1; j + i <= distance; j++) {
28 result[0] += left[i] * right[j];
29 }
30 }
31
32 int[] leaves = new int[distance + 1];
33 for (int i = 1; i < distance; i++) {
34 leaves[i + 1] = left[i] + right[i];
35 }
36 return leaves;
37 }
38}In Java, the approach follows a similar pattern as in C++. An array is used to track the leaf nodes from a particular node at given distances. The results from left and right discussions are used to count valid 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/* Like C, a C++ solution leverages advanced structures to track pair-wise leaf distance calculations efficiently within tree traversal. A rough sample plan provides guidance for completing a full solution. */C++ can take advantage of STL and more sophisticated data management for calculating and preloading distances, easing evaluation processes.