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

前言

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

---

习题

1.二叉树着色游戏

题目链接:1145. 二叉树着色游戏 - 力扣（LeetCode）

题面:

代码:

/*** 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.好叶子节点对的数量

题目链接: 1530. 好叶子节点对的数量 - 力扣（LeetCode）

题面:

附上大佬代码:

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;}
}

---

后言

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