leetcode周赛好叶子节点的数量

leetcode周赛好叶子节点的数量

给你二叉树的根节点 root 和一个整数 distance 。
如果二叉树中两个 叶 节点之间的 最短路径长度 小于或者等于 distance &＃xff0c;那它们就可以构成一组 好叶子节点对 。
返回树中 好叶子节点对的数量 。

输入&＃xff1a;root &＃61; [1,2,3,4,5,6,7], distance &＃61; 3
输出&＃xff1a;2
解释&＃xff1a;好叶子节点对为 [4,5] 和 [6,7] &＃xff0c;最短路径长度都是 2 。但是叶子节点对 [4,6] 不满足要求&＃xff0c;因为它们之间的最短路径长度为 4 。

提示&＃xff1a;

• tree 的节点数在 [1, 2^10] 范围内。
• 每个节点的值都在 [1, 100] 之间。
• 1 <&＃61; distance <&＃61; 10

注意本题返回叶子节点的对数。我开始还以为求子树的个数想了半个多小时&＃xff0c;后来再审题&＃xff0c;发现求对数&＃xff0c;那就简单了&＃xff0c;求出每个节点的左右子树&＃xff0c;都有哪些叶子节点&＃xff0c;深度是多少&＃xff0c;然后两个集合运算就行了&＃xff0c;最后在吧两个集合合并给上级节点。

class Solution {public int countPairs(TreeNode root, int distance) {this.distance &＃61; distance;List<Integer> list &＃61; traverse(root,0);return count;}private int count &＃61; 0;private int distance &＃61; 0;public List<Integer> traverse(TreeNode root,int depth) {if (root &＃61;&＃61; null) {return new LinkedList<>();}LinkedList<Integer> rl &＃61; new LinkedList<>();//为叶子节点直接返回if (root.left &＃61;&＃61; null && root.right &＃61;&＃61; null) {rl.add(depth);return rl;}List<Integer> left &＃61; new LinkedList<>();List<Integer> right &＃61; new LinkedList<>();if (root.left !&＃61; null)left &＃61; traverse(root.left,depth &＃43; 1);if (root.right !&＃61; null)right &＃61; traverse(root.right,depth &＃43; 1);//左右子树有一个没有&＃xff0c;就不用计算了&＃xff0c;直接返回if (left.size() &＃61;&＃61; 0) {return right;}if (right.size() &＃61;&＃61; 0) {return left;}//计算左右子树符合distance的对数for (int i &＃61; 0; i < left.size(); i&＃43;&＃43;) {int a &＃61; left.get(i);for (int j &＃61; 0; j < right.size(); j&＃43;&＃43;) {int b &＃61; right.get(j);if ((a - depth) &＃43; (b - depth) <&＃61; distance) {count&＃43;&＃43;;}}}//合并两个列表for (int i &＃61; 0; i < left.size(); i&＃43;&＃43;) {rl.add(left.get(i));}for (int i &＃61; 0; i < right.size(); i&＃43;&＃43;) {rl.add(right.get(i));}return rl;}
}


很简单的遍历问题&＃xff0c;别想复杂了就好&＃xff0c;这种返回list形式的题之前的周赛也遇到过。
leetcode 118