這是LeetCode上的一道題目，需要求二叉樹(shù)中兩點(diǎn)路徑的最大和。原題是

https://oj.leetcode.com/problems/binary-tree-maximum-path-sum/

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

For example: Given the below binary tree,

1/ \2 3

Return 6.

?

大概的想法其實(shí)很簡(jiǎn)單，類似于用分治法求數(shù)組連續(xù)和的最大值。最大值有三種可能，第一種是起點(diǎn)和終點(diǎn)最大和在左子樹(shù)中，第二種是起點(diǎn)和終點(diǎn)最大和在右子樹(shù)中，第三種是起點(diǎn)在左子樹(shù)中，終點(diǎn)在右子樹(shù)中。第三種要求路徑必須通過(guò)根節(jié)點(diǎn)，因此其左右子樹(shù)中的路徑只能是從左右子樹(shù)的根節(jié)點(diǎn)到其中的某個(gè)節(jié)點(diǎn)。根據(jù)這個(gè)思路，就可以寫(xiě)出如下的代碼。

class Solution { public:int maxPathSum(TreeNode *root) {if(root==NULL)return 0;else{if(root->left==NULL && root->right==NULL)return root->val;int maxLeft = maxPathSum(root->left);int maxRight = maxPathSum(root->right);int maxLeafLeft = max(0, maxLeafSum(root->left));int maxLeafRight = max(0, maxLeafSum(root->right));int sumWithRoot = root->val + maxLeafLeft + maxLeafRight;return max(maxLeft, maxRight, sumWithRoot);} }int maxLeafSum(TreeNode* root){if(root==NULL)return 0;else{if(root->left==NULL && root->right==NULL)return root->val;else{return root->val + max(maxLeafSum(root->left), maxLeafSum(root->right)); } } } }

這個(gè)方法雖然結(jié)果是正確的，但是很不幸嚴(yán)重超時(shí)。雖然我知道瓶頸是出在maxLeafSum()上，這其中有很多的冗余計(jì)算，但是沒(méi)有想到該如何優(yōu)化。后來(lái)看了別人的解答，才發(fā)現(xiàn)自己對(duì)遞歸的理解還是不夠深入。我參考了soulmachine的解答（順便說(shuō)一下，這個(gè)解答是我看過(guò)的最詳細(xì)的解答了 https://github.com/soulmachine/leetcode?），他用的代碼是

class Solution {public:int maxPathSum(TreeNode *root) {max_sum = INT_MIN;dfs(root);return max_sum;} private:int max_sum;int dfs(const TreeNode *root) {if (root == NULL) return 0;int l = dfs(root->left);int r = dfs(root->right);int sum = root->val;if (l > 0) sum += l;if (r > 0) sum += r;max_sum = max(max_sum, sum);return max(r, l) > 0 ? max(r, l) + root->val : root->val;} };

這里的DFS就是返回從根節(jié)點(diǎn)到某個(gè)子節(jié)點(diǎn)的路徑最大和。咋看一下似乎不對(duì)，怎么只考慮了路徑通過(guò)根節(jié)點(diǎn)的情形呢，即開(kāi)頭我們討論的第三種情形？這個(gè)地方的巧妙之處在于，我們所要求的最大和路徑必定是滿足其起點(diǎn)和終點(diǎn)在某個(gè)節(jié)點(diǎn)的兩側(cè)。所以只要我們用某個(gè)把這個(gè)函數(shù)應(yīng)用到所有節(jié)點(diǎn)之上，把每次的計(jì)算結(jié)果與一個(gè)全局變量比較，就可以得到正確的結(jié)果。

非常巧妙的方法！這也說(shuō)明遞歸有時(shí)候可以簡(jiǎn)化問(wèn)題，甚至想得越簡(jiǎn)單越好，只要我們保證最優(yōu)解肯定對(duì)于某個(gè)節(jié)點(diǎn)滿足我們給定的形式。

?

用類似的辦法可以計(jì)算二叉樹(shù)所有節(jié)點(diǎn)中的最大值、最小值。

?

轉(zhuǎn)載于:https://www.cnblogs.com/darkphoton/p/4141417.html

總結(jié)

以上是生活随笔為你收集整理的[Leetcode] Binary Tree Maximum Path Sum的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。