binary-tree-maximum-path-sum

题目描述

给定一个非空二叉树，返回其最大路径和。

本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

题解

自底向上？后序遍历？太卑微了，最终还是点开了答案。

使用 val 来记录全局最大路径和。lmr表示路径：left->middle->right，return表示路径：由左/右子树经过当前节点向上走。

int hmax(TreeNode* root, int &val) {
	if (root == nullptr)return 0;
	int left = max(hmax(root->left, val),0);
	int right = max(hmax(root->right, val),0);
	int lmr = root->val + left + right;
	val = max(val,lmr);
	return root->val + max(left, right);
}
int maxPathSum(TreeNode* root) {
	int val = INT_MIN;
	int k= hmax(root, val);
	return max(k, val);
}