二叉树着色游戏 图解题解

这道题到底在问什么

输入

root=[1..11], n=11, x=3

输出

true

输入

root=[1,2,3], n=3, x=1

输出

false

最优解：一步一步想明白

1. 3记牢这一句:x 把树切成左子树、右子树、父亲方向三块,二号去堵最大的一块,只要它比 n 的一半还大就赢。下面每一帧都在量这三块。
2. 4n = 11 个节点,值互不相同先看清这棵树。一共 11 个节点,值是 1 到 11 互不相同的整数(题目规定值是 1 到 n 的排列)。游戏规则是一号先在某个节点上落子,你二号再落一子,然后轮流向相邻节点蔓延。现在轮到一号先选了。
3. 5一号选 x = 3(橙色那个)一号把值为 3 的节点染了色,就是橙色这个。注意它一落子,整棵树就被它隔成了三块互不相通的区域:它的左子树、它的右子树、以及从它往上通向父亲的那一大片。我们要做的就是量清楚这三块各有多大。
4. 6DFS 找值为 3 的节点先得在树里把这个 x 找出来。从根 6 开始一路深搜:根的值是 6,不是我们要的 3,那就往孩子走,先去左边看看。
5. 7锁定 x = 3走到根的左孩子,值正好是 3,这就是一号落子的 x,锁定它。接下来分别量它的左子树、右子树,再算父亲方向那一块。
6. 8左子树从 2 开始数,l = 0先量左子树。从 3 的左孩子 2 进去,这一整块以后都归左子树。计数器 l 先记成 0,每数到一个节点就加一。
7. 9节点 2 计入左子树,l = 1节点 2 算进左子树,l 变成 1,把它标成蓝色表示已经数过。再看看节点 2 下面还有没有节点,有的话接着数。
8. 10节点 2 的左孩子是 1节点 2 还有个左孩子 1,走下去。1 是叶子,下面再没有节点了,但它仍然属于左子树,也得数进去。
9. 11节点 1 计入左子树,l = 2节点 1 算进去,l 变成 2。节点 1 没有孩子了,左子树这一支也就到头了。
10. 12左子树 = 两个节点,l = 2左子树数完了,一共节点 2 和 1 两个节点,l 等于 2。蓝色这一小块就是二号如果选左孩子能独占的区域。记住这个 2,接着量右边。
11. 13右子树从 4 开始数,r = 0再量右子树。左块的蓝色先留着别动,从 3 的右孩子 4 进去,计数器 r 从 0 起步,同样数一个加一个。
12. 14节点 4 计入右子树,r = 1节点 4 算进右子树,r 变成 1,把它标成绿色,跟左块的蓝色区分开。再看节点 4 下面还挂着谁。
13. 15节点 4 的右孩子是 5节点 4 有个右孩子 5,走下去。5 也是叶子,下面没有别的节点,但它仍归右子树,继续数进去。
14. 16节点 5 计入右子树,r = 2节点 5 算进去,r 变成 2。节点 5 没有孩子,右子树这一支也到头了。
15. 17右子树 = 两个节点,r = 2右子树数完,节点 4 和 5 两个,r 等于 2。绿色这一块就是二号如果选右孩子能独占的区域。现在左块 2、右块 2,只剩最后一块还没算。
16. 18x 加左右子树 = 1 + 2 + 2 = 5把 x 自己,加上它的左子树和右子树,1 加 2 加 2 等于 5,这 5 个节点是「x 这一坨」。整棵树 11 个,刨掉这 5 个,剩下的全都在 x 往上的父亲方向。
17. 19父亲方向 = 11 - 2 - 2 - 1 = 6父亲方向那一块不用一个个数,直接用总数 11 减掉 x 这一坨 5,等于 6。也就是图上那 6 个还没上色的节点:6、9、7、10、8、11,它们都在 x 的上方。
18. 20三块大小:2 / 2 / 6三块全量出来了:左子树 2 个,右子树 2 个,父亲方向 6 个。一眼就看出来,父亲方向那块最大。二号要赢,就该往最大的这块去堵。
19. 21max(2, 2, 6) = 6,n // 2 = 5取三块里最大的 6,再看 n 的一半:11 除以 2 向下取整是 5。6 严格大于 5,说明只要二号占住父亲方向那 6 个,就已经过了半数,这局稳赢。
20. 22y 选 3 的父亲 6,独占父亲方向 6 个具体怎么落子?二号把 y 放在 3 的父亲、也就是根 6 上。这一子像一道闸门,把一号死死封在它自己那 5 个节点里,而二号顺着父亲方向能把那 6 个全染蓝。
21. 23二号 6 个 > 一号 5 个 ➜ true最后一清点:二号 6 个,一号 5 个,6 比 5 多,二号赢。所以这道题答案是 true。整个过程没真去模拟一回合一回合的染色,只靠量出三块、堵最大那块,一步就判了输赢。
22. 24量三块,堵最大,过半即赢回放一遍:x 把树切成 2、2、6 三块,最大的一块 6 超过了一半,二号就把 y 贴在那一块的入口堵上,稳赢。要是三块最大的都不过半,那二号怎么下都赢不了,返回 false。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

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

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

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

复杂度

面试官可能追问