二叉树：二叉树的最大路径和

二叉树的最大路径和，枚举二叉树的每一个节点，通过当前节点最大路径和是， 当前节点左子树的最大路径和 root->val 当前节点右子树的最大路径。

代码语言：javascript复制

struct node {
	int val;
	node *left, *right;
};

int ans = MIN_MAX;//用于维护最大路径和
int dfs(node *root) {
	if (!root) return 0;
	int left  = dfs(root->left);
	int right = dfs(root->right);
	ans = max(ans, max(root->val left right);
	return max(0, root->val   max(0, max(left, right)));
}


int maxPathSum(node* root) {
	dfs(root);
	return ans;
}

二叉树

0 人点赞