二叉树着色游戏 图解题解

选完 x，二号还有没有机会染得更多

树上 n 个节点、n 是奇数，值 1 到 n 互不相同。一号先挑值 x 的节点染红，二号挑另一个值 y 染蓝，之后轮流把自己染过节点的未染相邻节点（左、右孩子或父节点）接着染，谁都动不了才结束，染得多的赢。问能否找到 y 让二号多于一号。题面两例：root=[1,2,3,4,5,6,7,8,9,10,11]、x=3 返 true，root=[1,2,3]、x=1 返 false。

真把这盘棋一回合回合走完，会卡在哪

照规则把染色模拟一遍是最像直觉的打算：每选一个 y 就推演整局看谁多。可 y 有 n-1 种选法，每种都要模拟到填满棋盘，慢且易在蔓延顺序上错。它更漏了个一步定音的事实：x 一落下，胜负就已锁死。

x 一落子，棋就被切成互不相通的三块

x 这个节点是一堵墙：从它出发只有左子树、右子树、父亲往上三个方向，块与块之间的唯一通道都要过 x，而 x 归了一号，谁也穿不过去。所以二号把 y 紧贴 x 放，就能独占某一整块。

二号最多能拿三块里最大的一块，大小分别是左子树节点数 l、右子树节点数 r、父亲方向 n-l-r-1（刨去 x 和其左右子树）。判赢要最大块严格＞n//2：n 是奇数没平局，最大块恰好等于 n//2 时二号也没过半，剩下都归一号。

代码只做两件事：找到 x，数它的左右子树

先一趟 DFS，也就是深搜、顺一条路走到底再回头，找值等于 x 的节点：遇空或命中就返回，否则先左后右（Python 的 dfs(left) or dfs(right) 靠短路，左边有就不看右边）。拿到 x 后各数一遍左右子树得 l、r，父亲方向不必数，用 n-l-r-1 减出。最后 max(l, r, n-l-r-1) 与 n//2 比，大于返回 true。

两个题面例子，各自量出三块

root=[1,2,3,4,5,6,7,8,9,10,11]、x=3：按层序摆开，3 是根 1 的右孩子，左孩子 6、右孩子 7 都是叶子。左子树只有 6，l=1；右子树只有 7，r=1；父亲方向 11-1-1-1=8。三块是 1、1、8，最大 8；n//2=5，8＞5，返回 true。

root=[1,2,3]、x=1：根就是 x，左右孩子 2、3 各是一个叶子，l=1、r=1；x 是根、头顶没有节点，父亲方向 3-1-1-1=0。三块是 1、1、0，最大 1；n//2=1，最大块 1 并没有严格＞1，返回 false。这正是打平半数、二号赢不了的情形：占个叶子，反被守根的一号多染一个。

算得快不是难点，难在别把三块漏了一块

复杂度：找 x 最坏扫遍全树 O(n)，数子树也不超过 O(n)，合起来仍是 O(n)。占空间的是递归栈、深度等于树高：平衡时约 O(log n)，退化成链时 O(n)。

几处一写就反：只比左右子树、忘了父亲方向那块，可它常常最大，漏掉会把能赢判成不能赢；判赢用大于等于 n//2，会在最大块恰好等于半数时误判二号赢。边角想清：n=1 时二号无子可染永远 false，x 是叶子时父亲方向独占 n-1 个、多半稳赢。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def btreeGameWinningMove(self, root: Optional[TreeNode], n: int, x: int) -> bool:
        def dfs(root):
            if root is None or root.val == x:
                return root
            return dfs(root.left) or dfs(root.right)

        def count(root):
            if root is None:
                return 0
            return 1 + count(root.left) + count(root.right)

        node = dfs(root)
        l, r = count(node.left), count(node.right)
        return max(l, r, n - l - r - 1) > n // 2

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool btreeGameWinningMove(TreeNode* root, int n, int x) {
        auto node = dfs(root, x);
        int l = count(node->left), r = count(node->right);
        return max({l, r, n - l - r - 1}) > n / 2;
    }

    TreeNode* dfs(TreeNode* root, int x) {
        if (!root || root->val == x) {
            return root;
        }
        auto node = dfs(root->left, x);
        return node ? node : dfs(root->right, x);
    }

    int count(TreeNode* root) {
        if (!root) {
            return 0;
        }
        return 1 + count(root->left) + count(root->right);
    }
};

Java

import java.util.*;
/**
 * 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 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 ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    public boolean btreeGameWinningMove(TreeNode root, int n, int x) {
        TreeNode node = dfs(root, x);
        int l = count(node.left);
        int r = count(node.right);
        return Math.max(Math.max(l, r), n - l - r - 1) > n / 2;
    }

    private TreeNode dfs(TreeNode root, int x) {
        if (root == null || root.val == x) {
            return root;
        }
        TreeNode node = dfs(root.left, x);
        return node == null ? dfs(root.right, x) : node;
    }

    private int count(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return 1 + count(root.left) + count(root.right);
    }
}