去年准备Google面试的时候就见过这道题，现在leetcode上竟然有了。
对方的点把整个图（想象成一个graph）分为了三个部分，我们最优策略就是选择最大的那一枝，贴着对面的点放置我们的点。由此，这道题的本质变成了计算subtree节点数的题目。
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: int left, right, val; bool btreeGameWinningMove(TreeNode* root, int n, int x) { val = x; dfs(root); return max(n-left-right-1,max(left,right))>n/2; } int dfs(TreeNode *root){ if (root==NULL) return 0; int l=dfs(root->left), r=dfs(root->right); if (root->val==val){ left = l; right=r; } return l+r+1; } };
时间复杂度 O(n)
Followup 如果先手怎么办
类似minimax，让对手能着色的最大枝最小。
LeetCode 1145. Binary Tree Coloring Game
原文：https://www.cnblogs.com/hankunyan/p/11495418.html