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

题目

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

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

思路

简单题，dfs返回当前节点为一端的最大链。答案有两种情况，1 当前节点到子孙的一条链 2 当前节点为中端，两端为子孙。

class Solution { public: int MAX = INT_MIN; public: int maxPathSum(TreeNode* root) { maxPath(root); return MAX; } int maxPath(TreeNode* root){ if(root == nullptr) return 0; int R = maxPath(root->right); int L = maxPath(root->left); MAX = max(MAX,R+L+root->val); MAX = max(MAX,root->val + max(0,max(R,L))); return root->val + max(0,max(R,L)); } };