很简单的题，真的。解决方案
很简单的题，真的。
给一棵二叉树，证明一定可以把它的节点分成三个部分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满足结论。
命题得证。
------解决方案--------------------
给一棵二叉树，证明一定可以把它的节点分成三个部分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满足结论。
命题得证。
------解决方案--------------------