leetcode周赛好叶子节点的数量

八月 13, 2020

leetcode周赛好叶子节点的数量

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

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

提示：

tree 的节点数在 [1, 2^10] 范围内。

每个节点的值都在 [1, 100] 之间。

1 <= distance <= 10

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

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

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

查看评论