2019-T5 about ustc-cs-graduate HOT 3 CLOSED

struct TreeNode {
	int val;
	TreeNode* left;
	TreeNode* right;

	TreeNode() {};
	TreeNode(int x) :val(x) {};
	TreeNode(int x, TreeNode* l, TreeNode* r) :val(x), left(l),right(r) {};
};

struct info {
	int low;
	int up;
	info(int a, int b) : low(a), up(b) {};
};


int gb_ret;
int maxChainLen(TreeNode* root) {
	if (!root) return 0;

	int llen = maxChainLen(root->left);
	int rlen = maxChainLen(root->right);

	//若去掉这行关于全局变量gb_ret的代码，那maxChainLen就是求从某个结点向下的最长路径
	//若保留，则：
	//每次递归走到此处时，我们已经知道了从左、右走的两条最长路，那么我们也就知道了在该点“拐弯”的最长路径
	//又由于maxChainLen会遍历所以结点，那我们相应地也就穷举了在所有点“拐弯”的路径
	gb_ret = fmax(root->val + llen + rlen, gb_ret);

	return fmax(llen, rlen) + root->val;
}


void t5() {
	int k;
	ifstream fin("tree.in");
	TreeNode* root;

	queue<pair<TreeNode**, info*>> q;
	pair<TreeNode**, info*> rootpair = { &root, new info(-1,INT32_MAX) };
	q.push(rootpair);
	while (fin >> k) {
		TreeNode** T;
		info* ifm;
		while (true) {
			T = q.front().first;
			ifm = q.front().second;
			q.pop();

			if (ifm->low < k && k < ifm->up) {
				break;
			}
		}
		
		*T = new TreeNode(k, NULL, NULL);
		//注意->优先于&
		pair<TreeNode**, info*> leftpair = { &(*T)->left, new info(ifm->low, k) };
		pair<TreeNode**, info*> rightpair = { &(*T)->right, new info(k,ifm->up) };

		q.push(leftpair);
		q.push(rightpair);
	}

	gb_ret = -1;
	maxChainLen(root);
	cout << gb_ret;
}