二叉树上的占领游戏

ygmm 发表于 2019-3-28 13:58
我觉得
return a > sum / 2 || b > sum / 2 || c > sum / 2;这个判断条件 在== sum/2 的时候返回false ...

中间一个 是平手

补充内容 (2019-3-28 14:03):
怎么删掉这条？

说一下我的思路，大家指正

先手的棋手落子后，根据落子的地点以及树的形状，有以下几种情况：
- 当起手点是叶子节点时，原有的树还是一个连通图，而后手棋手只要落子在次叶子节点的父节点则后手棋手必胜，因次先手棋手通常不应该选择叶子节点
- 当起手点是跟节点，或非根非叶子节点且其左右子树有一个为空时，原有的树被切割成两个联通子图，后手棋手只能选择两个联通图中节点多的一个，若两个联通图中节点数目相同，则后手棋手必败。
- 当起手点是非根非叶子节点且其左右子树均不为空时，原有的树被切割成三个联通子图，左子树L，右子树R，以及树中其他剩余节点P，此时后手棋手必定选择其中含有节点数最多的一个子图，因此，当先手棋手选择的点满足：MAX(L, R, P) < SUM(!MAX(L,R,P)) 即：最多的子图节点数小于剩余两个子图节点数的和，则后手棋手必败。

比较有意思的讨论是：在一颗树中，是否一定能找到必胜的节点？这样的节点是否有多于一个？

summernight 发表于 2019-4-2 11:12
说一下我的思路，大家指正

先手的棋手落子后，根据落子的地点以及树的形状，有以下几种情况：

感觉等于的情况也是后手必败？因为先手在放第一个棋子的时候已经得了一分了

ziwei1992 发表于 2019-4-12 11:59
感觉等于的情况也是后手必败？因为先手在放第一个棋子的时候已经得了一分了

是说第三种情况吧？对的，如果等于也是后手必败，我说得不够严谨

这道题让我想起了
stellaris
emmm
卡点

hmm
大佬们
假设对手的点选为node1
1 先计算以node1为根的子树所有node1的个数n1，然后再计算除去这棵子树剩余节点的个数n2
2 如果n2大于n1，则选node1的parent为开始，则必胜
3 如果n2小于n1，则计算node1的左子树所有node的个数nl和右子树所有node的个数nr
4 如果nl > n1-nl, 则选node1的左儿子
5 如果nr > n1-nr， 则选node1的右儿子
6 如果以上都莫得，则不能胜利

大佬们系不系啊
跪求大佬们给我改改


补充内容 (2019-4-13 04:27):
hmmm 不对不对

搞错了 没有考虑 往上发展的情况

楼下是改正

从4 开始

4 如果nl > n1+n2 -nl, 则选node1的左儿子
5 如果nr > n1+n2 -nr, 则选node1的右儿子
6 其余莫得

补充内容 (2019-4-13 04:30):
不对这个也不对
4：nl > max(n2+1, n1-nl) node的左儿子
5：nr >max(n2+1, n1-nr)node的右儿子

大佬们帮忙看看呗
给你们加分呦

如果是follow up的话
则 对于每个在树上的node算以下的点：
n0：所有node个数n0
n1: 以这个node为root的子树的node数
n2: 或左或右子树的node数

然后比较三种占子情况即（爹，左儿子，右儿子）
最后得出呗

补充内容 (2019-4-13 04:36):
各位大佬99萌新哈

我好像在leetcode还是哪里看到过这题。但是想不起来了。。

raistlins 发表于 2019-4-13 06:13
我好像在leetcode还是哪里看到过这题。但是想不起来了。。

有谁知道leetcode 题号？