split tree(C++)

这个代码没测试过。 
5.1. an arbitrary tree. split it into as many subtrees as you can. the
number of nodes of the subtree must be even.
递归呗. 不算难. 只是树的描述应该是
struct Node{
    int data;
    list<Node *> nodes;
};
------------------------
思路：每个node记录左子树和右子树的node的个数。随便找种顺序遍历树，对每个node的子树，是偶数就砍掉，是奇数就留着。递归做被砍掉的树。

void findnumber(Node *root, map<Node *,int> &num){
  if(!root) {num[root] = 0; return;}
  num[root] = 1;
  list<Node *>::iterator it = root->nodes.begin();
 while( it++ != root->nodes.end() ){
   findnumber(it,num);
   num[root] += num[it];
 }
}

void dfscut(Node *root, map<Node *, int> num, vector<Node *> &res){
   list<Node *>::iterator it = root->nodes.begin();
   while( it != root->nodes.end() ){
      if(num[it] & 1 == 1) { it++;}
      else {
        dfscut(it, num, res);
        it = root->nodes.erase(it);
       num[root] -= num[it];
      }
  }

res.push_back(root);
}


vector<Node *> cutTree(Node *root){
  map<Node *, int> num;
  vector<Node *> res;
  findnumber(root, num);
  if(num[root] & 1 == 1) return NULL;
  dfscut(root, num, res);

return res;
}