很简单的题，真的。
给一棵二叉树，证明一定可以把它的节点分成三个部分A,B,C使得每一对父子节点在不同的集合中，并使得max{|A|,|B|,|C|}-min{|A|,|B|,|C|}≤1
[解决办法]
归纳法证明
1）对节点个数为1的二叉树 显然结论成立。
2）假设对节点为n的二叉树 结论成立即存在A，B,C的划分使得：max{
[解决办法]
A
[解决办法]
,
[解决办法]
B
[解决办法]
,
[解决办法]
C
[解决办法]
}-min{
[解决办法]
A
[解决办法]
,
[解决办法]
B
[解决办法]
,
[解决办法]
C
[解决办法]
}≤1
现在考察节点为n+1二叉树。因为节点为n+1的二叉树。去掉其根节点后，可形成左右两个二叉树+root节点。我们命名左树伟 l_tree 右树伟r_tree。同时左右数的节点都<= n 因此
左树可划分三个集合A1,B1,C1： max{
[解决办法]
A1
[解决办法]
,
[解决办法]
B1
[解决办法]
,
[解决办法]
C1
[解决办法]
}-min{
[解决办法]
A1
[解决办法]
,
------解决方案--------------------
B1
[解决办法]
,
[解决办法]
C1
[解决办法]
}≤1
右树可划分三个集合A2,B2,C2： max{
[解决办法]
A2
[解决办法]
,
[解决办法]
B2
[解决办法]
,
[解决办法]
C2
[解决办法]
}-min{
[解决办法]
A2
[解决办法]
,
[解决办法]
B2
[解决办法]
,
[解决办法]
C2
[解决办法]
}≤1
不妨设其中A1，A2为最大集合，C1,C2为最小集合。
因此对整个n+1节点树 我们可以构建集合A = A1+C2, B=B1+B2,C=C1+A2。显然A ,B，C都没有父子节点在一个集合中。
对：
[解决办法]
A
[解决办法]
-
[解决办法]
B
[解决办法]
=
[解决办法]
A1
[解决办法]
+
[解决办法]
C2
[解决办法]
-
[解决办法]
B1
[解决办法]
-
[解决办法]
B2
[解决办法]
=
------解决方案--------------------
A1
[解决办法]
-
[解决办法]
B1
[解决办法]
-(
[解决办法]
B2
[解决办法]
-
[解决办法]
C2
[解决办法]
)
[解决办法]
A1
[解决办法]
-
[解决办法]
B1
[解决办法]
<=1,
[解决办法]
B2-C2
[解决办法]
<=1。两个小于等于1的整数相减必然是小于等于1.
对
[解决办法]
A
[解决办法]
-
[解决办法]
C
[解决办法]
,
[解决办法]
B
[解决办法]
-
[解决办法]
C
[解决办法]
,
[解决办法]
C
[解决办法]
-
[解决办法]
B
[解决办法]
都有同样的结论。 因此当节点为n+1时候同样存在集合A，B,C满足结论。
命题得证。
[解决办法]
