有这样一个题目，描述如下：
给定一个二叉树，每个节点具备一个权重值，按照如下规则选取二叉树中的节点，如果选取了某个节点，那么其子节点都不能被选取了。在这个规则下面，如何保证选取的和最大。
关于二叉树有一些系列的基本问题：
这一类问题基本上都可以利用二叉树的递归遍历方式来处理，根据题目要求的不同，可能采取先序，后序或者中序遍历等等。其中最大的不同也就是递归过程中的某些处理。往往感到棘手的也就是如何写这个递归过程，总有一种似是而非的感觉。其实当想清除一个问题之后，处理递归来就顺手很多，在回溯过程中，已经得到子问题的最优解，再思考如何将这个子问题的最优解和当前的节点比较或处理就可以。典型的是将二叉树改为双向链表，使用一个指针pre记住前一个节点，那么在某次回溯的过程中，意味着前面的节点已经构成双向链表了，如何处理好现在的节点与pre的关系就ok了。因为每次递归调用都是同样的代码。
对于这个问题，类似于动态规划，从根节点出发，找到其左子树和右子树的最优解，判断其和是否大于根节点的权重，若是的，则根节点放弃。依次递归，判断每个节点的左右子树的最大值与该节点的值的大小关系。很显然，我们如果从叶子节点往上走，就可以在一次遍历过程中，完成全部的工作。
基于上面的分析，写出下面的代码，还包括回溯打印选中的节点的过程。整个递归的代码很简洁，不超过十行。
#include<iostream>
#include<vector>
#include<iterator>
using namespace std;
typedef struct tree{
int value;
struct tree *left;
struct tree *right;
tree(int val, tree* l, tree* r){
value = val;
left = l;
right = r;
}
}BinaryTree;
void inorder(BinaryTree *root){
if(root == NULL)
return;
inorder(root->left);
cout << root->value << " ";
inorder(root->right);
}
void partytime(BinaryTree *root,int *weight){
if(root == NULL)
return;
int left = 0, right = 0;
partytime(root->left,&left);
partytime(root->right,&right);
if(left + right > root->value){
*weight = left + right;
}else{
*weight = root->value;
}
}
void partytime(BinaryTree *root,int *weight,vector<int>& vec){
if(root == NULL)
return;
int left = 0, right = 0;
partytime(root->left,&left,vec);
partytime(root->right,&right,vec);
if(left + right > root->value){
*weight = left+right;
}else
*weight = root->value;
vec.push_back(*weight);
}
void tracingback(BinaryTree *node,vector<int>& vec,int index){
if(node == NULL || vec.size() <= index)
return;
if(node->value == vec.at(index)){
cout << node->value << " ";
return;
}
int i = 0;
for(i; i < index; i++){
if(vec[i] == vec.at(index)-vec.at(index-1))
break;
}
tracingback(node->left,vec,i);
tracingback(node->right,vec,index-1);
}
int main(){
BinaryTree one(4,NULL,NULL);
BinaryTree tmp(5,NULL,NULL);
BinaryTree two(3,&one,&tmp);
BinaryTree thr(2,NULL,NULL);
BinaryTree fou(12,&thr,&two);
BinaryTree fiv(3,NULL,NULL);
BinaryTree six(6,NULL,&fiv);
BinaryTree sev(2,NULL,NULL);
BinaryTree egi(5,&six,&sev);
BinaryTree root(10,&fou,&egi);
inorder(&root);
cout << endl;
int weight = 0;
vector<int> vec;
partytime(&root,&weight);
partytime(&root,&weight,vec);
copy(vec.begin(),vec.end(),ostream_iterator<int,char>(cout," "));
cout << endl;
cout << "tracing back: ";
tracingback(&root,vec,vec.size()-1);
cout << endl;
return 0;
}
写递归的代码，切记需要把递归的过程想清楚，这样若需要将递归转换到循环来处理时，会更加顺手。