树型DP

算法概论第九周

文章目录

• 树型DP
• • 题目描述
  • 思路分析
  • 实现代码

124 Binary Tree Maximum Path Sum 题目链接

题目描述

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.

Example 1:

Input: [1,2,3]

       1
      / \
     2   3

Output: 6
Example 2:

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

   -10
   / \
  9  20
    /  \
   15   7

Output: 42
           

思路分析

• 这道题可以采用树型动态规划的方式求解
• 定义每个节点有一个记录值 m e m mem mem，表示以该点为起点，终点为叶节点的最长路径值

• m e m mem mem可能连接左子树，也可能连接右子树，也可能仅包含一个点

  m e m [ n o w ] = v a l [ n o w ] + m a x { m e m [ l e f t ] , m e m [ r i g h t ] , 0 } mem[now] = val[now] + max\{mem[left], mem[right],0\} mem[now]=val[now]+max{mem[left],mem[right],0}

• 题目所求的路径，最多只会有一个“拐点”，即路径有可能包含一个节点的左右及其左右子树
• 为了计算路径最长，我们可以利用一个变量 h i s t o r y M a x historyMax historyMax来记录递归过程中的最大路径

• 最长路径可以是左子树构成的mem值对应路径，也可以是右子树构成的mem值对应路径，也可以是左右加顶点构成，也可以仅一个顶点

  h i s t o r y M a x = m a x { h i s t o r y M a x , v a l [ n o w ] , m e m [ l e f t ] , m e m [ r i g h t ] , m e m [ l e f t ] + m e m [ r i g h t ] } historyMax = max\{historyMax,val[now],mem[left],mem[right],mem[left]+mem[right] \} historyMax=max{historyMax,val[now],mem[left],mem[right],mem[left]+mem[right]}

• 同时，我们可以使用记忆化递归的方式记录 m e m mem mem值，设当前节点索引为 i n d e x index index，左节点为 i n d e x ∗ 2 + 1 index * 2 + 1 index∗2+1，右节点为 i n d e x ∗ 2 + 2 index * 2 + 2 index∗2+2。但由于题目数据刁钻， 最后的AC代码并没有使用记忆化……

实现代码

其中注释掉的部分为记忆化搜索部分

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
// const int MAXNUM = 20000000;
// int mem[MAXNUM];
class Solution {
    int historyMax = -10000000;
public:
    int maxPathSum(TreeNode* root) {
        // for(int i = 0; i < MAXNUM; i++){
        //     mem[i] = -1;
        // }
        findMax(root, 0);
        return historyMax;
    }
    int findMax(TreeNode* root, int ind){
        // if(mem[ind] != -1)
        // return mem[ind];
        if(root == NULL){
            // mem[ind] = 0;
            return 0;
        }
        int maxleft = findMax(root->left, ind * 2 + 1);
        int maxright = findMax(root->right, ind * 2 + 2);
        int res = max(root->val, root->val + max(maxleft, maxright));
        historyMax = max(historyMax, res);
        historyMax = max(historyMax, root->val + maxleft + maxright);
        historyMax = max(historyMax, root->val);
        return res;
    }
};