很简单的题，真的。

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

赞。
归纳法可证。