樹型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;
    }
};