Binary Tree Maximum Path Sum

week4

难度：Hard

题目链接

题目描述

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

For this problem, a path is defined as any sequence of nodes 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.

Example1:

Input: [1,2,3]

       1
      / \
     2   3

Output: 6

Example2:

Input: [-10,9,20,null,null,15,7]

   -10
   / \
  9  20
    /  \
   15   7

Output: 42

题目分析

  这道题目要求找出一颗二叉树中的得到最大数之和的一条路径，路径中的头和尾可以是二叉树中的任意一节点。这也就是说除了可以经过根节点外，还可以是二叉树里任意子树，只要得到的和为最大。

解题思路

  首先想到的是用递归的算法，来算出每一个节点作为根节点所得到的最大路径和，这和书上第四章的某道题目有点相像：已知两顶点，求出两个顶点存在多少条路径。当时我们可以使用递归方式分别求出上一层到下一层节点有多少条路径，逐步计算出到达每一层的路径，最后得到总的路径数。
  这道题目也是这样，子树的最大路径和可以是左子树+根+右子树等等，但其作为上一层的子节点只能是左子树/右子树+根。因此我们判断长度和返回到上一层的值是不一样的。即maxNum = max(leftNum + rightNum + node->val,maxNum);(若左右子树<0，则设其为0)和返回的值return node->val + sumNum;

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/* *
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
#include <algorithm>
class Solution {
public:
    int maxNum;
    int maxPathSum(TreeNode* root) {
        if(root != nullptr)
        {
            maxNum = root->val;
        }
        sumPath(root);
        return maxNum;
    }

    int sumPath(TreeNode * node)
    {
        if(node == nullptr)
        {
            return 0;
        }
        int leftNum = sumPath(node->left);//求左右子节点的最大路径和
        int rightNum = sumPath(node->right);
        if(leftNum < 0)
        {
            leftNum = 0;
        }
        if(rightNum < 0)
        {
            rightNum = 0;
        }
        int sumNum = max(leftNum,rightNum);
        maxNum = max(leftNum + rightNum + node->val,maxNum);//每一次和原本的值作比较
        return node->val + sumNum;
    }
};

Note

  1. 有可能存在只有一个节点，所以一开始最大和设为根节点的值，也可以设置成INT_MIN，因为可能最终的值是负数。

  2. 因为不一定经过根节点的就是路径最大和，而且每一颗子树都有可能是目标树或者一个特别大的节点，所以每次递归都要进行一次比较，以求得最大的值。

  3. 做完之后发现代码运行好像很慢，比较了一下和大佬的代码，发现还是写的太复杂了一点，有一些判断根本是不必要的，比如判断是否<0等，直接用max取最大的就可以了，因为负数不是不合法的，不会产生什么逻辑错误。

  4. 此外发现大佬的代码中写了这么一句速度看起来比我的快不少。。。在网上查了下之后似乎是cin、cout效率低的原因是要把东西输入到缓冲区在进行输入输出，这一句语句可以取消其缓冲，使得和scanf、printf的效率差不多。。这也解释了为什么以前有时候用cin和cout会超时，而用scanf、printf不会。

1
static int fast = []() {ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); return 0; }();

  附上大佬简洁的代码。。但感觉阅读上可能并不会很快，可能有时候需要在简洁和易懂中作出取舍

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
static int fast = []() {ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); return 0; }();
class Solution {
public:
    int go(TreeNode* t, int& Ans) { //maxPathSum through t
        if (!t) return 0;
        int L = go(t->left, Ans), R = go(t->right, Ans), Ret = 0;
        Ret = max(t->val, t->val + max(L, R));
        Ans = max(Ans, max(L + R + t->val, Ret));
        return Ret;
    }
    int maxPathSum(TreeNode* t) {
        int Ans = INT_MIN;
        go(t, Ans);
        return Ans;
    }
};