iT邦幫忙

1

資結經典題目: 在二元樹中找最長路徑和

今天跟大家分享一道LeetCode上的題目

參考題目: LeetCode- 124. Binary Tree Maximum Path Sum
(相關子題: LeetCode- 543. Diameter of Binary Tree)

題目說給你一個非空的二元樹,求最大的路徑和,
至少要包含一個節點,
路徑不一定要通過root
例子:

input:
   -10
   / \
  9  20
    /  \
   15   7
output: 42 (15-20-7有最大路徑和42)

Note: 本題樹結構的定義為

/**
 * 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) {}
 * };
 */

你可以直接使用TreeNode。

解法一、有點暴力的解,耗時1292ms

首先定義兩個函數輔助解題:

  1. int maxSinglePathPassRoot(TreeNode* root): 計算通過root的單向路徑最大總和(只能往左邊或往右邊走),如果root為空則只好回傳0,否則至少要包含root的值
  2. int maxPathPassRoot(TreeNode* root): 計算通過root的路徑最大總和,把左右兩邊最大路徑加總就是了

題目要實作的函數是int maxPathSum(TreeNode* root),如果可以對整棵樹的每個點呼叫maxPathPassRoot即可找到答案。但可以看到maxSinglePathPassRoot這個函數被重複呼叫多次,故非常浪費時間。

class Solution {
public:
    int maxSinglePathPassRoot(TreeNode* root){
        if(root==NULL){
            return 0;
        }
        int left = max(0,maxSinglePathPassRoot(root->left));
        int right = max(0,maxSinglePathPassRoot(root->right));
        return root->val+max(left, right);
        
    }
    
    int maxPathPassRoot(TreeNode* root){
        if(root==NULL){
            return 0;
        }
        int left = max(0,maxSinglePathPassRoot(root->left));
        int right = max(0,maxSinglePathPassRoot(root->right));
        return root->val+left+right;
    }
    
    int maxPathSum(TreeNode* root) {
        int M = maxPathPassRoot(root);
        if(root->left){
            M = max(M, maxPathSum(root->left));
        }
        if(root->right){
            M = max(M, maxPathSum(root->right));
        }
        return M;
    }
};

解法二、改良版,呼叫 maxSinglePathPassRoot時即更新最大值,耗時40ms

解法一可以優化成這樣,在呼叫maxSinglePathPassRoot的時候,其實已經知道每個節點做為root時,一定要通過那個節點的路徑最大值(即root->val+left+right),可以邊遞迴呼叫時一邊更新最大值,不必再透過額外的函數maxPathPassRoot來做。

class Solution {
public:
    int maxSinglePathPassRoot(TreeNode* root, int &MAX){
        if(root==NULL){
            return 0;
        }
        int left = max(0,maxSinglePathPassRoot(root->left, MAX));
        int right = max(0,maxSinglePathPassRoot(root->right, MAX));
        MAX = max(MAX, root->val + left+ right);
        return root->val+max(left, right);
    }
    
    int maxPathSum(TreeNode* root) {
        int M = root->val;
        maxSinglePathPassRoot(root, M);
        return M;
    }
};

補充- LeetCode- 543. Diameter of Binary Tree

題目給你一個二元樹,找最長路徑的長度(不一定要通過root)
其實只要把上一題用到root->val的地方改成1就行了,
解法如下:

class Solution {
public:
    int maxSinglePathPassRoot(TreeNode* root, int &MAX){
        if(root==NULL){
            return 0;
        }
        int left = max(0,maxSinglePathPassRoot(root->left, MAX));
        int right = max(0,maxSinglePathPassRoot(root->right, MAX));
        MAX = max(MAX, 1 + left+ right);
        return 1+max(left, right);
    }

    
    int diameterOfBinaryTree(TreeNode* root) {
        if(root==NULL){
            return 0;
        }
        int M = 0;
        maxSinglePathPassRoot(root, M);
        return M-1;
    }
};

尚未有邦友留言

立即登入留言