空空的数据课程设计实验

main.cpp

#include <algorithm>
#include <iostream>
#include <sstream>
using namespace std;

struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	int maxvIfChoose;
	int maxvIfNotChoose;
	TreeNode(int val) {
		this->val = val;
		left = NULL;
		right = NULL;
	}
};

void buildTree(TreeNode *&root, stringstream *in) {
	int value;
	*in >> value;
	if (value == 0) return;
	
	root = new TreeNode(value);
	buildTree(root->left, in);
	buildTree(root->right, in);
}

void solveTree(TreeNode *root) {
	root->maxvIfChoose = root->val;
	root->maxvIfNotChoose = 0;

	//solveLeft: 
	if (root->left != NULL) {
		solveTree(root->left);
		root->maxvIfNotChoose += max(root->left->maxvIfChoose, root->left->maxvIfNotChoose);
		root->maxvIfChoose += root->left->maxvIfNotChoose;
	}
	//solveRight:
	if (root->right != NULL) {
		solveTree(root->right);
		root->maxvIfNotChoose += max(root->right->maxvIfChoose, root->right->maxvIfNotChoose);
		root->maxvIfChoose += root->right->maxvIfNotChoose;
	}
}

void deleteTree(TreeNode *root) {
	if (root != NULL) {
		deleteTree(root->left);
		deleteTree(root->right);
		delete root;
	}
}

int solve(string input) {
	stringstream *treestream = new stringstream(input);
	TreeNode *root = NULL;
	buildTree(root, treestream);
	delete treestream;

	if (root != NULL) {
		solveTree(root);
		int res = max(root->maxvIfChoose, root->maxvIfNotChoose);
		deleteTree(root);
		return res;
	}
	else {
		return -9999999; // 不可能到这个分支里
	}
}

int main() {
	string line;
	while (getline(cin, line)) {
		int res = solve(line);
		cout << res << '\n';
	}
}