Number of Good Leaf Nodes Pairs

class Solution {
private:
    vector<int> traverseAndCollect(TreeNode* node, int dist) {
        if (!node)
            return vector<int>(12);
        else if (!node->left && !node->right) {
            vector<int> leafDistances(12);
            leafDistances[0] = 1;
            return leafDistances;
        }

        vector<int> leftSubtree = traverseAndCollect(node->left, dist);
        vector<int> rightSubtree = traverseAndCollect(node->right, dist);

        vector<int> accumulated(12);
        for (int i = 0; i < 10; i++) {
            accumulated[i + 1] = leftSubtree[i] + rightSubtree[i];
        }

        accumulated[11] += leftSubtree[11] + rightSubtree[11];

        int cumulativeSum = 0;
        int index = 0;
        for (int offset = dist - 2; offset >= 0; offset--) {
            cumulativeSum += leftSubtree[index++];
            accumulated[11] += cumulativeSum * rightSubtree[offset];
        }

        return accumulated;
    }

public:
    int countPairs(TreeNode* root, int dist) {
        return traverseAndCollect(root, dist)[11];
    }
};

The given C++ solution is designed to count the number of good leaf node pairs in a binary tree where the distance between them is less than or equal to a specified number. The solution employs a recursive approach to solve the problem by defining a function traverseAndCollect that is used to explore the tree and collect the required data for computation.

• The traverseAndCollect function:

  • Takes a TreeNode* node and an integer dist as parameters.
  • Base case check: If the node is NULL, the function returns a zero-initialized vector of size 12.
  • Leaf node check: If the node is a leaf (no children), it initializes a vector of size 12 with the first element set to 1, representing a leaf node at distance 0.
  • Recursively collects data from the left and right subtrees.
  • Aggregates the results from both subtrees.
  • Computes potential pairs of leaf nodes where one leaf comes from the left subtree and the other from the right subtree, counting only those pairs where the distance between leaves does not exceed the given dist.

• The countPairs function:

  • Utilizes traverseAndCollect starting from the root of the binary tree.
  • Returns the total count of good leaf pairs from the last element of the result of traverseAndCollect.

This approach ensures that each leaf node is considered precisely once for each pair (avoiding double counting), and efficiently accumulates the count of valid leaf pairs as the recursion unfolds, leveraging postorder traversal properties.

class Solution {

    public int computePairs(TreeNode root, int maxDist) {
        return explore(root, maxDist)[11];
    }

    private int[] explore(TreeNode node, int maxDist) {
        if (node == null) return new int[12];
        else if (node.left == null && node.right == null) {
            int[] leafCounts = new int[12];
            leafCounts[0] = 1;
            return leafCounts;
        }

        int[] leftSubtree = explore(node.left, maxDist);
        int[] rightSubtree = explore(node.right, maxDist);

        int[] leafDistances = new int[12];
        for (int j = 0; j < 10; j++) {
            leafDistances[j + 1] = leftSubtree[j] + rightSubtree[j];
        }

        leafDistances[11] = leftSubtree[11] + rightSubtree[11];

        int accumulatedSum = 0;
        int k = 0;
        for (int distanceRemaining = maxDist - 2; distanceRemaining >= 0; distanceRemaining--) {
            accumulatedSum += leftSubtree[k++];
            leafDistances[11] += accumulatedSum * rightSubtree[distanceRemaining];
        }

        return leafDistances;
    }
}

The Java solution for finding the number of good leaf nodes pairs involves computing the number of pairs of leaf nodes that are within a given distance from each other in a binary tree, defined by the maxDist parameter. Here's a breakdown of how the solution is implemented:

1. Define a method computePairs(TreeNode root, int maxDist) which calls the auxiliary method explore with the root node and the distance constraint.
2. Implement the method explore(TreeNode node, int maxDist):
   • If the current node is null, return an array of size 12 initialized to zero. This array tracks the number of leaves at various distances up to 11.
   • If the node is a leaf (both left and right children are null), initialize an array of size 12, setting the first element to 1, indicating a leaf node at distance 0.
   • Recursively call explore for the left and right subtrees to obtain their distances.
   • Calculate the sum of leaf nodes for distances up to 10 from the current node by adding corresponding distances from the left and right subtrees.
   • Calculate the number of good leaf node pairs using the given maxDist. For each possible distance, count pairs of leaf nodes from left and right subtrees that together do not exceed maxDist - 2.
   • Update the total count of good pairs in the final position, i.e., the 12th location of the array.

By the end of this process, the 12th index of the array returned by explore on the root node contains the total count of all good leaf node pairs within the specified maximum distance, effectively solving the problem.

class Solution:
    def _traverse_post_order(self, node, max_distance):
        if node is None:
            return [0] * 12
        elif node.left is None and node.right is None:
            leaf = [0] * 12
            leaf[0] = 1
            return leaf

        left_subtree = self._traverse_post_order(node.left, max_distance)
        right_subtree = self._traverse_post_order(node.right, max_distance)

        combined = [0] * 12

        for idx in range(10):
            combined[idx + 1] = left_subtree[idx] + right_subtree[idx]

        combined[11] = left_subtree[11] + right_subtree[11]

        running_sum = 0
        index = 0
        for dist in range(max_distance - 2, -1, -1):
            running_sum += left_subtree[index]
            combined[11] += running_sum * right_subtree[dist]
            index += 1

        return combined

    def countGoodPairs(self, root: TreeNode, distance: int) -> int:
        return self._traverse_post_order(root, distance)[11]

This Python code defines a class Solution to solve the problem of counting all pairs of good leaf nodes in a binary tree where the distance between them is less than or equal to a given value.

• The key function _traverse_post_order is implemented to perform a post-order traversal of the binary tree to gather information on the distribution of leaf node distances for both the left and right subtree.
• It uses a list to maintain the count of leaves at each distance from the root up to a maximum of 11 levels, considering constraints of the problem.
• On encountering a leaf node, it initializes a 12-element list leaf with the count of leaf at distance 0 set to 1.
• For non-leaf nodes, the method sums the counts of leaf nodes from the left and right children up to a specified maximum distance, shifting indices to accommodate parent-to-child distances.
• It also calculates possible good pairs from separate subtrees, considering the given distance constraint.
• countGoodPairs is the externally accessible function that starts the traversal and returns the total count of good leaf pairs from the result of _traverse_post_order.

Apply these functions by defining a binary tree with TreeNode objects and pass the root node alongside the maximum acceptable distance between leaf nodes to the method countGoodPairs to get the required result.