博客

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

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

思路：


这道题，首先要正确理解题目意思。返回一个最大路径和，很容易想到用递归地方法，将子节点的路径和求出，加上自身就是该节点为根的路径和。题目的要求是从任意节点出发，而不是子树的根节点出发，因此要将左右子树的路径和都加上才符合题意。

当然，计算中需要判断左右子树路径和加自身节点值是否变小（也就是子树路径小于0）

	int sum_max =INT_MIN;
    int maxPathSum(TreeNode* root) {
        int ans = 0;

        //深先用优先搜索吧
        dfs(root);
        return sum_max;
    }

    int dfs(TreeNode* node)
    {

        if(node == nullptr)
        {
            return 0;
        }
        int val = node->val;
        int sum_left = dfs(node->left);
        int sum_right = dfs(node->right);
        int sum_all = val+sum_left+sum_right;

        val = max(max(val+sum_left, val + sum_right), val);
        int sum = max(val, sum_all);

        sum_max = max(sum, sum_max);
        return val;
    }