1530. Number of Good Leaf Nodes Pairs

class Solution {
    private static class Pair {
        private final List<Integer> leafDistanceList;
        private int count;

        public Pair() {
            this.leafDistanceList = new ArrayList<>();
            this.count = 0;
        }
    }

    public int countPairs(TreeNode root, int distance) {
        return dfs(root, distance).count;
    }

    private Pair dfs(TreeNode root, int distance) {
        Pair pair = new Pair();

        if (root == null) {
            return pair;
        }
        if (root.left == null && root.right == null) {
            pair.leafDistanceList.add(0);
            return pair;
        }

        Pair left = dfs(root.left, distance);
        Pair right = dfs(root.right, distance);

        pair.count += left.count + right.count;

        for (int leftDistance : left.leafDistanceList) {
            for (int rightDistance : right.leafDistanceList) {
                if (leftDistance + rightDistance + 2 <= distance) {
                    pair.count += 1;
                }
            }
        }

        for (int leftDistance : left.leafDistanceList) {
            pair.leafDistanceList.add(leftDistance + 1);
        }
        for (int rightDistance : right.leafDistanceList) {
            pair.leafDistanceList.add(rightDistance + 1);
        }

        return pair;
    }
}

使用后序遍历解题。

References

1530. Number of Good Leaf Nodes Pairs