0x00 题目

有两位极客玩家参与了一场「二叉树着色」的游戏
游戏中，给出二叉树的根节点 root，树上总共有 n 个节点
且 n 为奇数，其中每个节点上的值从 1 到 n 各不相同

游戏从「一号」玩家开始（「一号」玩家为红色，「二号」玩家为蓝色）
最开始时

「一号」玩家从 [1, n] 中取一个值 x（1 <= x <= n）

「二号」玩家也从 [1, n] 中取一个值 y（1 <= y <= n）且 y != x

「一号」玩家给值为 x 的节点染上红色，而「二号」玩家给值为 y 的节点染上蓝色

之后两位玩家轮流进行操作
每一回合，玩家选择一个他之前涂好颜色的节点
将所选节点一个 未着色 的邻节点（即左右子节点、或父节点）进行染色

如果当前玩家无法找到这样的节点来染色时，他的回合就会被跳过

若两个玩家都没有可以染色的节点时，游戏结束
着色节点最多的那位玩家获得胜利

现在，假设你是「二号」玩家，根据所给出的输入
假如存在一个 y 值可以确保你赢得这场游戏
则返回 true；若无法获胜，就请返回 false

0x01 思路

以 x 为观察点
整棵树被分为 3 个部分
左子树部分
右子树部分
整棵树 减去 以 x 为根的树，剩余的部分
如果其中一个部分(a)比剩余部分(n-a)多
则说明能赢

0x02 解法

语言：Swift

树节点：TreeNode

public class TreeNode {    public var val: Int    public var left: TreeNode?    public var right: TreeNode?    public init() { self.val = 0; self.left = nil; self.right = nil; }    public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }    public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {        self.val = val        self.left = left        self.right = right    }}

解法：

func btreeGameWinningMove(_ root: TreeNode?, _ n: Int, _ x: Int) -> Bool {    // 左子树个数，右子树个数    var left = 0, right = 0    func dfs(_ root: TreeNode?, _ x: Int) -> Int {        guard let root = root else { return 0 }        let l = dfs(root.left, x)        let r = dfs(root.right, x)        // 当前节点为目标节点，记录左右子树节点个数        if root.val == x {            left = l            right = r        }        // 当前节点总数        return l + r + 1    }    _ = dfs(root, x)    // 以 x 为根的树，总节点数量    let t = left + right + 1        // 另外一部分的树，节点总数足够多    let b1 = n - t > t        // 左分支，节点总数足够多    let b2 = left > n - left        // 右分支，节点总数足够多    let b3 = right > n - right    if b1 || b2 || b3 {        return true    }    return false}

0x03 我的作品

欢迎体验我的作品之一：小笔记-XNote
让笔记一步到位！
App Store 搜索即可~