每日算法系列【LeetCode 124】二叉树中的最大路径和

题目描述

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

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

示例1

输入:
[1,2,3]

      1
     / \
    2   3
输出:
6

示例2

输入:
[-10,9,20,null,null,15,7]

     -10
     / \
    9  20
      /  \
     15   7
输出:
42

题解

这是一道树形 dp 入门题,也就是树上的动态规划。

首先要理解它这个输入什么意思,虽然写代码的时候不用你管,已经给你处理成结构体了。
输入是一个数组,其实是二叉树的层次遍历,也就是从第一层(根结点)开始,往下一层一层遍历结点,同一层从左往右遍历。

这题要求的是一条路径,路径上的数字之和要最大。
我们采用递归来做这题,假设dfs(r)表示以 r 为根结点的子树中最长路径的和,而左右子结点用 l 和 r 来表示

那么有人可能会说,这不是很简单了嘛。
一共就下面几种情况:

  1. 只取根结点:r->val
  2. 只取左子树:dfs(l)
  3. 只取右子树:dfs(r)
  4. 取根结点和左子树:r->val + dfs(l)
  5. 取根结点和右子树:r->val + dfs(r)
  6. 取根结点和左子树和右子树:r->val + dfs(l) + dfs(r)

最后的答案就是dfs(root)

然而这样对吗?其实是错的,刚开始我也犯了这样的错误(好久没做树形 dp 了,见笑了)。
为什么是错的呢?试想这么一种情况,万一左子树的最优解是不经过左子结点的话,怎么与根结点连接起来呢?
这种情况下你的计算就有问题了,所以我们必须加强一下之前的假设。

这次我们假设dfs(r)表示以 r 为根结点的子树中经过根结点 r 的最长路径的和。
现在继续分成上面的几种情况讨论,然而最后的dfs(root)意思变了,指的是必须经过根结点 root 的最优路径之和。
那怎么办呢?很好办,只需要用一个全局变量,每次递归的时候都更新一下最大值就行了,因为总有一个结点是最优路径所在子树的根结点。

分析到这里,貌似都对了,但是还有问题吗?
注意看上面的第2、3、6三种情况,如果最优情况是这三种,然后用它们更新dfs(r),会出现什么情况?
情况2、3会导致回溯之后,在根结点 r 处断开了,也就是不经过 r 了,那再高层也就没法求解了。
而情况6会导致路径出现左右分叉,这也是不允许的。
所以递归的最后更新时,只能用其他三种情况更新。

代码

c++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int res = INT_MIN;

    int maxPathSum(TreeNode* root) {
        dfs(root);
        return res;
    }

    int dfs(TreeNode* root) {
        if (root == NULL) return 0;
        int l_max_sum = dfs(root->left);
        int r_max_sum = dfs(root->right);
        int sum = root->val;
        sum = max(sum, sum + l_max_sum);
        sum = max(sum, sum + r_max_sum);
        res = max(res, sum);
        return max({0, l_max_sum, r_max_sum}) + root->val;
    }
};

python

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    res = -sys.maxsize

    def maxPathSum(self, root: TreeNode) -> int:
        self.dfs(root)
        return self.res

    def dfs(self, root: TreeNode) -> int:
        if root == None:
            return 0
        l_max_sum = self.dfs(root.left)
        r_max_sum = self.dfs(root.right)
        sum = root.val
        sum = max(sum, sum + l_max_sum)
        sum = max(sum, sum + r_max_sum)
        self.res = max(self.res, sum)
        return max(0, l_max_sum, r_max_sum) + root.val

后记

这题虽然是困难题,但是也是树形 dp 的入门题,思考起来和实现起来 trick 还是挺多的。


   转载规则


《每日算法系列【LeetCode 124】二叉树中的最大路径和》 韦阳 采用 知识共享署名 4.0 国际许可协议 进行许可。
 上一篇
5W2H | 关于写博客的七点反思 5W2H | 关于写博客的七点反思
When?什么时候开始写的?第一次写博客是 2015 年了,在 CSDN 和博客园上面,当时写文章是为了记录 ACM 竞赛的题解,陆陆续续写了几十篇。但是最后还是没有坚持下去,主要还是因为 CSDN 和博客园的体验太差了,写起文章来很难受
2020-01-14
下一篇 
每日算法系列【LeetCode 357】计算各个位数不同的数字个数 每日算法系列【LeetCode 357】计算各个位数不同的数字个数
题目描述给定一个非负整数 n ,计算各位数字都不同的数字 x 的个数,其中 $0 \le x < 10^n$ 。 示例1 输入: 2 输出: 91 解释: 答案应为除去 11,22,33,44,55,66,77,88,99 外,在
2020-01-12
  目录