360检测网站开发语言的工具,pc网站手机网站app,广东建设职业技术学院官方网站,吉林网站建设业务文章目录 题目标题和出处难度题目描述要求示例数据范围 解法思路和算法代码复杂度分析 题目
标题和出处
标题#xff1a;二叉树着色游戏
出处#xff1a;1145. 二叉树着色游戏
难度
6 级
题目描述
要求
两位玩家参与二叉树着色游戏。给定二叉树的根结点 root \textt… 文章目录 题目标题和出处难度题目描述要求示例数据范围 解法思路和算法代码复杂度分析 题目
标题和出处
标题二叉树着色游戏
出处1145. 二叉树着色游戏
难度
6 级
题目描述
要求
两位玩家参与二叉树着色游戏。给定二叉树的根结点 root \texttt{root} root以及树中的结点数目 n \texttt{n} n n \texttt{n} n 是奇数且每个结点的值从 1 \texttt{1} 1 到 n \texttt{n} n 各不相同。
初始时第一位玩家选择一个值 x \texttt{x} x满足 1 ≤ x ≤ n \texttt{1} \le \texttt{x} \le \texttt{n} 1≤x≤n第二位玩家选择一个值 y \texttt{y} y满足 1 ≤ y ≤ n \texttt{1} \le \texttt{y} \le \texttt{n} 1≤y≤n 且 y ≠ x \texttt{y} \ne \texttt{x} yx。第一位玩家将值为 x \texttt{x} x 的结点涂上红色第二位玩家将值为 y \texttt{y} y 的结点涂上蓝色。
之后从第一位玩家开始两位玩家轮流操作。每一轮玩家选择自己颜色的结点第一位玩家选择红色第二位玩家选择蓝色将所选结点的一个未涂色的相邻结点左子结点、右子结点或者父结点涂上颜色。
当且仅当一位玩家无法按照该规则选择结点时该玩家必须跳过当前轮次。如果两位玩家都跳过当前轮次游戏结束涂色结点更多的玩家是获胜方。
你是第二位玩家。如果可能选择一个 y \texttt{y} y 确保你赢得游戏返回 true \texttt{true} true。如果不可能返回 false \texttt{false} false。
示例
示例 1 输入 root [1,2,3,4,5,6,7,8,9,10,11], n 11, x 3 \texttt{root [1,2,3,4,5,6,7,8,9,10,11], n 11, x 3} root [1,2,3,4,5,6,7,8,9,10,11], n 11, x 3 输出 true \texttt{true} true 解释第二位玩家可以选择值为 2 \texttt{2} 2 的结点。
示例 2
输入 root [1,2,3], n 3, x 1 \texttt{root [1,2,3], n 3, x 1} root [1,2,3], n 3, x 1 输出 false \texttt{false} false
数据范围
树中结点数目是 n \texttt{n} n 1 ≤ x ≤ n ≤ 100 \texttt{1} \le \texttt{x} \le \texttt{n} \le \texttt{100} 1≤x≤n≤100 n \texttt{n} n 是奇数 1 ≤ Node.val ≤ n \texttt{1} \le \texttt{Node.val} \le \texttt{n} 1≤Node.val≤n树中的所有值各不相同
解法
思路和算法
由于二叉树中的结点数目是 n n n每个结点的值从 1 1 1 到 n n n 各不相同 1 ≤ x ≤ n 1 \le x \le n 1≤x≤n因此二叉树中存在唯一的值为 x x x 的结点该结点称为结点 x x x。
首先使用深度优先搜索在二叉树中定位到结点 x x x结点 x x x 将二叉树中的其余 n − 1 n - 1 n−1 个结点分成三个部分结点 x x x 的左子树、结点 x x x 的右子树和其余结点每个部分各为一个连通区域不同部分之间不连通每个部分的结点数最少为 0 0 0最多为 n − 1 n - 1 n−1三个部分的结点数总和为 n − 1 n - 1 n−1。
根据游戏规则每一位玩家在分别选择第一个涂色的结点之后每次选择涂色的结点都必须和己方已经涂色的结点相邻因此同一位玩家涂色的结点一定总是相连的。由于结点 x x x 被第一位玩家涂色因此第二位玩家选择的结点 y y y 一定属于三个部分之一且当第二位玩家选择结点 y y y 之后只能在同一个部分继续涂色。
第二位玩家为了赢得游戏选择的结点 y y y 应该使得己方可以涂色的结点数最多因此结点 y y y 应该位于结点数最多的一个部分。只要结点 y y y 和结点 x x x 相邻第二位玩家即可确保结点 y y y 所在的部分的所有结点都可以由第二位玩家涂色。为了使得结点 y y y 和结点 x x x 相邻结点 y y y 应为结点 x x x 的左子结点、右子结点或者父结点由于结点 y y y 所在的部分的结点数一定大于 0 0 0因此结点 y y y 不为空。
除了结点 y y y 所在的部分以外其余结点都由第一位玩家涂色因此判断第二位玩家是否可以赢得游戏的依据是结点 y y y 所在的部分的结点数是否大于其余结点数总和。由于二叉树中的结点数目 n n n 是奇数因此第二位玩家可以赢得游戏等价于结点 y y y 所在的部分的结点数至少为 n 1 2 \dfrac{n 1}{2} 2n1。
由于第二位玩家选择的结点 y y y 应该位于结点数最多的一个部分因此只需要判断三个部分的结点数中的最大值是否至少为 n 1 2 \dfrac{n 1}{2} 2n1即可知道第二位玩家是否可以赢得游戏。
计算三个部分的结点数的方法为对结点 x x x 的左子树和右子树分别使用深度优先搜索计算结点数左子树和右子树的结点数分别记为 leftCount \textit{leftCount} leftCount 和 rightCount \textit{rightCount} rightCount剩下的一个部分的结点数为 n − 1 − leftCount − rightCount n - 1 - \textit{leftCount} - \textit{rightCount} n−1−leftCount−rightCount。只要有一个部分的结点数至少为 n 1 2 \dfrac{n 1}{2} 2n1则返回 true \text{true} true否则返回 false \text{false} false。
代码
class Solution {TreeNode xNode;public boolean btreeGameWinningMove(TreeNode root, int n, int x) {search(root, x);int threshold (n 1) / 2;int leftCount countSubtreeNodes(xNode.left);if (leftCount threshold) {return true;}int rightCount countSubtreeNodes(xNode.right);if (rightCount threshold) {return true;}int remain n - 1 - leftCount - rightCount;return remain threshold;}public void search(TreeNode node, int x) {if (xNode ! null || node null) {return;}if (node.val x) {xNode node;return;}search(node.left, x);search(node.right, x);}public int countSubtreeNodes(TreeNode node) {if (node null) {return 0;}return 1 countSubtreeNodes(node.left) countSubtreeNodes(node.right);}
}复杂度分析 时间复杂度 O ( n ) O(n) O(n)其中 n n n 是二叉树的结点数。定位到结点 x x x 和计算二叉树每个部分的结点数的过程中每个结点最多被访问一次。 空间复杂度 O ( n ) O(n) O(n)其中 n n n 是二叉树的结点数。空间复杂度主要是递归调用的栈空间取决于二叉树的高度最坏情况下二叉树的高度是 O ( n ) O(n) O(n)。
