Leetcode 124. 二叉树中的最大路径和

题目

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

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

示例 1:

输入: [1,2,3]1/ \2   3输出: 6

示例 2:

输入: [-10,9,20,null,null,15,7]-10/ \9  20/  \15   7输出: 42

题解

递归，递归返回经过父节点要经过该节点的最大路径和
显然，我们返回的应该是本节点+左子树或右子树的最大路径和。同时在函数中，我们好需要判断不走父节点，只走该节点的最大路径和，也就是左子树+右子树+本节点的最大路径和。
详细过程见代码

代码

	int search(TreeNode* root,int &val){if(root == NULL)    return 0;int left = search(root->left,val);int right = search(root->right,val);int sum = root->val + max(0,left) + max(0,right);	//不走父节点int only = root->val + max(0,max(left,right));		//允许走父节点val = max(val,max(sum,only));return only;}int maxPathSum(TreeNode* root) {int val = INT_MIN;search(root,val);return val;}

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-maximum-path-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。