力扣-数据结构-15【算法学习day.86】

前言

###我做这类文章一个重要的目的还是给正在学习的大家提供方向（例如想要掌握基础用法，该刷哪些题？建议灵神的题单和代码随想录）和记录自己的学习过程，我的解析也不会做的非常详细，只会提供思路和一些关键点，力扣上的大佬们的题解质量是非常非常高滴！！！

习题

1.二叉树着色游戏

题目链接:

题面:

代码:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int[] flag;
    int sonl = 0;
    int sonr = 0;
    int x;
    public boolean btreeGameWinningMove(TreeNode root, int n, int x) {
        this.x = x;
        flag = new int[n+1];
        if(x==root.val){
            int l = recursion(root.left);
            int r = recursion(root.right);
            return l==r?false:true;
        }else{
            int sum = recursion(root);
            if(sonl!=0&&sonr!=0){
                int l = flag[sonl];
                int r = flag[sonr];
                if((sum-l)<l||(sum-r)<r){
                return true;
            }
        }
            int re = sum - flag[x];
            return re>flag[x]?true:false;
        }
    }
    public int recursion(TreeNode node){
        if(node==null)return 0;
        int l = recursion(node.left);
        int r = recursion(node.right);
        flag[node.val] = l+r+1;
        if(node.val==x&&node.left!=null&&node.right!=null){
            sonl = node.left.val;
            sonr = node.right.val;
        }
        return l+r+1;
    }
}

2.好叶子节点对的数量

题目链接: 

题面:

附上大佬代码:

class Solution {
    int pairs = 0;

    public int countPairs(TreeNode root, int distance) {
        getDistances(root, distance);
        return pairs;
    }

    public List<Integer> getDistances(TreeNode node, int distance) {
        List<Integer> distances = new ArrayList<Integer>();
        if (node == null) {
            return distances;
        }
        if (node.left == null && node.right == null) {
            distances.add(0);
            return distances;
        }
        List<Integer> leftDistances = getDistances(node.left, distance);
        List<Integer> rightDistances = getDistances(node.right, distance);
        int leftSize = leftDistances.size();
        int rightSize = rightDistances.size();
        for (int i = 0; i < leftSize; i++) {
            int leftDistance = leftDistances.get(i) + 1;
            leftDistances.set(i, leftDistance);
            if (leftDistance <= distance) {
                distances.add(leftDistance);
            }
        }
        for (int i = 0; i < rightSize; i++) {
            int rightDistance = rightDistances.get(i) + 1;
            rightDistances.set(i, rightDistance);
            if (rightDistance <= distance) {
                distances.add(rightDistance);
            }
        }
        for (int leftDistance : leftDistances) {
            for (int rightDistance : rightDistances) {
                if (leftDistance + rightDistance <= distance) {
                    pairs++;
                }
            }
        }
        return distances;
    }
}

后言

上面是相关的习题，下一篇文章会将其他相关的习题。