[Leetcode]124. Binary Tree Maximum Path Sum(C++)

题目描述

Given a non-empty binary tree, find the maximum path sum.

For this problem, a path is defined as any node sequence from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

例子

例子建议通过官方题目描述中察看二叉树的示例图方便理解结构

例子 1

Input: root = [1,2,3] Output: 6

例子 2

Input: root = [-10,9,20,null,null,15,7] Output: 42

Follow Up

Note

Constraints

The number of nodes in the tree is in the range [0, 3 * 10^4].

-1000 <= Node.val <= 1000

解题思路

这道题关键是要理解题目中对路径的定义，理解对一个根节点有几种情况。理解之后再结合递归方法可以求解，题目中的路径的定义是可以是树中任意两个节点的通路，可以不通过根节点。并且题目中还隐含着一个意思，即每个节点只能通过 1 遍，意味着任意两个节点之间的通路只有一条。了解了题目的意思之后，我们来看一下对于一个根节点，满足条件的路径有几种情况：

经过根节点
不经过根节点，可以在左子树中或者右子树中

对于第二种情况，我们很容易想到可以通过递归的方式继续判断，那么可以继续深入考虑第一种情况，如果是要经过根节点的话，我们需要获取三个值，分别是：

根节点的值
左子树的最大的子路径和（注意这里的子路径表示该路径的其中一个端点必须是左子树根节点，否则不能和根节点连接）
右子树的最大的子路径和（要求同上）

因此对递归函数（这里用 DFS 搜索），要做以下几件事情：

计算左子树和右子树的最大子路径和
计算经过当前根节点的最大路径和（根节点不一定是端点，可以同时取两侧子树最大路径和）并更新结果（这里的结果是最终要返回的结果）
返回当前以根节点为端点的最大路径和（左子树和右子树的最大路径和只能选一个）

代码如下：

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
 * right(right) {}
 * };
 */
class Solution {
public:
    int maxPathSum(TreeNode* root) {
        result = INT_MIN;
        dfs(root);
        return result;
    }

private:
    int result;
    int dfs(TreeNode* root) {
        if (!root) return 0;

        // max path sum that go through this node and its
        // left & right subtree
        int sum = root->val;

        // max path sum that go through this node and one of its subtree
        int left_path = root->val;
        int right_path = root->val;

        int left_sum = dfs(root->left);
        if (left_sum > 0) {
            sum += left_sum;
            left_path += left_sum;
        }

        int right_sum = dfs(root->right);
        if (right_sum > 0) {
            sum += right_sum;
            right_path += right_sum;
        }

        result = max(result, sum);
        return max(left_path, right_path);
    }
};

时间复杂度: O(n)
空间复杂度: O(h) – 递归深度

GitHub 代码同步地址： 124.BinaryTreeMaximumPathSum.cpp

其他题目： GitHub: Leetcode-C++-Solution 博客： Leetcode-Solutions