Binary Tree Maximum Path Sum · 數據結構與算法/leetcode/lintcode題解

# Binary Tree Maximum Path Sum ### Source - lintcode: [(94) Binary Tree Maximum Path Sum](http://www.lintcode.com/en/problem/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. Example Given the below binary tree, 1 / \ 2 3 Return 6. ~~~ ### 題解1 - 遞歸中僅返回子樹路徑長度如題目右側的四顆半五角星所示，本題屬于中等偏難的那一類題。題目很短，要求返回最大路徑和。咋看一下感覺使用遞歸應該很快就能搞定，實則不然，**因為從題目來看路徑和中不一定包含根節點！也就是說可以起止于樹中任一連通節點。** 弄懂題意后我們就來剖析剖析，本著由簡入難的原則，我們先來分析若路徑和包含根節點，如何才能使其路徑和達到最大呢？選定根節點后，路徑和中必然包含有根節點的值，剩下的部分則為左子樹和右子樹，要使路徑和最大，則必然要使左子樹和右子樹中的路徑長度都取最大。 ****> 注意區分包含根節點的路徑和(題目要的答案)和左子樹/右子樹部分的路徑長度(答案的一個組成部分)。路徑和=根節點+左子樹路徑長度+右子樹路徑長度 ~~~ -10 / \ 2 -3 / \ / \ 3 4 5 7 ~~~ 如上所示，包含根節點`-10`的路徑和組成的節點應為`4 -> 2 -> -10 <- -3 <- 7`, 對于左子樹而言，其可能的路徑組成節點為`3 -> 2`或`4 -> 2`, 而不是像根節點的路徑和那樣為`3 -> 2 <- 4`. 這種差異也就造成了我們不能很愉快地使用遞歸來求得最大路徑和。我們使用分治的思想來分析路徑和/左子樹/右子樹，設 f(root)f(root)f(root) 為`root`的子樹到`root`節點(含)路徑長度的最大值，那么我們有f(root)=root?>val+max(f(root?>left),?f(root?>right))f(root) = root->val + \max (f(root->left), ~f(root->right))f(root)=root?>val+max(f(root?>left),?f(root?>right)) 遞歸模型已初步建立起來，接下來就是分析如何將左右子樹的路徑長度和最終題目要求的「路徑和」掛鉤。設 g(root)g(root)g(root) 為當「路徑和」中根節點為`root`時的值，那么我們有g(root)=root?>val+f(root?>left)+f(root?>right)g(root) = root->val + f(root->left) + f(root->right)g(root)=root?>val+f(root?>left)+f(root?>right) 順著這個思路，我們可以遍歷樹中的每一個節點求得 g(node)g(node)g(node) 的值，輸出最大值即可。如果不采取任何記憶化存儲的措施，其時間復雜度必然是指數級別的。嗯，先來看看這個思路的具體實現，后續再對其進行優化。遍歷節點我們使用遞歸版的前序遍歷，求單邊路徑長度采用遞歸。 ### C++ Recursion + Iteration(Not Recommended) **Time Limit Exceeded** ~~~ /** * Definition of TreeNode: * class TreeNode { * public: * int val; * TreeNode *left, *right; * TreeNode(int val) { * this->val = val; * this->left = this->right = NULL; * } * } */ class Solution { public: /** * @param root: The root of binary tree. * @return: An integer */ int maxPathSum(TreeNode *root) { if (NULL == root) { return 0; } int result = INT_MIN; stack<TreeNode *> s; s.push(root); while (!s.empty()) { TreeNode *node = s.top(); s.pop(); int temp_path_sum = node->val + singlePathSum(node->left) \ + singlePathSum(node->right); if (temp_path_sum > result) { result = temp_path_sum; } if (NULL != node->right) s.push(node->right); if (NULL != node->left) s.push(node->left); } return result; } private: int singlePathSum(TreeNode *root) { if (NULL == root) { return 0; } int path_sum = max(singlePathSum(root->left), singlePathSum(root->right)); return max(0, (root->val + path_sum)); } }; ~~~ ### 源碼分析注意`singlePathSum`中最后的返回值，如果其路徑長度`path_sum`比0還小，那么取這一段路徑反而會減少最終的路徑和，故不應取這一段，我們使用0表示這一隱含意義。 ### 題解2 - 遞歸中同時返回子樹路徑長度和路徑和 ### C++ using std::pair 上題求路徑和和左右子樹路徑長度是分開求得的，因此導致了時間復雜度劇增的惡劣情況，從題解的遞推關系我們可以看出其實是可以在一次遞歸調用過程中同時求得路徑和和左右子樹的路徑長度的，只不過此時遞歸程序需要返回的不再是一個值，而是路徑長度和路徑和這一組值！C++中我們可以使用`pair`或者自定義新的數據類型來相對優雅的解決。 ~~~ /** * Definition of TreeNode: * class TreeNode { * public: * int val; * TreeNode *left, *right; * TreeNode(int val) { * this->val = val; * this->left = this->right = NULL; * } * } */ class Solution { private: pair<int, int> helper(TreeNode *root) { if (NULL == root) { return make_pair(0, INT_MIN); } pair<int, int> leftTree = helper(root->left); pair<int, int> rightTree = helper(root->right); int single_path_sum = max(leftTree.first, rightTree.first) + root->val; single_path_sum = max(0, single_path_sum); int max_sub_sum = max(leftTree.second, rightTree.second); int max_path_sum = root->val + leftTree.first + rightTree.first; max_path_sum = max(max_sub_sum, max_path_sum); return make_pair(single_path_sum, max_path_sum); } public: /** * @param root: The root of binary tree. * @return: An integer */ int maxPathSum(TreeNode *root) { if (NULL == root) { return 0; } return helper(root).second; } }; ~~~ ### 源碼分析除了使用`pair`對其進行封裝，也可使用嵌套類新建一包含單路徑長度和全局路徑和兩個變量的類，不過我用 C++寫的沒編譯過... 老是提示`...private`，遂用`pair`改寫之。建議使用`class`而不是`pair`封裝`single_path_sum`和`max_path_sum`[pair_is_harmful](#). 這種方法難以理解的地方在于這種實現方式的正確性，較為關鍵的語句為`max_path_sum = max(max_sub_sum, max_path_sum)`, 這行代碼是如何體現題目中以下的這句話的呢？ > The path may start and end at any node in the tree. 簡單來講，題解2從兩個方面予以保證： 1. 采用「冒泡」法返回不經過根節點的路徑和的較大值。 1. 遞推子樹路徑長度(不變值)而不是到該節點的路徑和(有可能變化)，從而保證了這種解法的正確性。如果還不理解的建議就以上面那個根節點為-10的例子畫一畫。 ### C++ using self-defined class ~~~ /** * Definition of TreeNode: * class TreeNode { * public: * int val; * TreeNode *left, *right; * TreeNode(int val) { * this->val = val; * this->left = this->right = NULL; * } * } */ class Solution { class ResultType { public: int singlePath, maxPath; ResultType(int s, int m):singlePath(s), maxPath(m) {} }; private: ResultType helper(TreeNode *root) { if (root == NULL) { ResultType *nullResult = new ResultType(0, INT_MIN); return *nullResult; } // Divide ResultType left = helper(root->left); ResultType right = helper(root->right); // Conquer int singlePath = max(left.singlePath, right.singlePath) + root->val; singlePath = max(singlePath, 0); int maxPath = max(left.maxPath, right.maxPath); maxPath = max(maxPath, left.singlePath + right.singlePath + root->val); ResultType *result = new ResultType(singlePath, maxPath); return *result; } public: int maxPathSum(TreeNode *root) { ResultType result = helper(root); return result.maxPath; } }; ~~~ ### 源碼分析 1. 如果不用 `ResultType *XXX = new ResultType ...` 再 `return *XXX` 的方式，則需要在自定義 class 中重載 `new` operator。 1. 如果遇到 `...private` 的編譯錯誤，則是因為自定義 class 中需要把成員聲明為 public，否則需要把訪問這個成員的函數也做 class 內部處理。 ### Reference - pair_is_harmful > . [std::pair considered harmful! ? Modern Maintainable Code](http://maintainablecode.logdown.com/posts/158531-stdpair-considered-harmful) > - 作者指出了 `pair` > 不能濫用的原因，如不可維護，信息量小。 [ ?](# "Jump back to footnote [pair_is_harmful] in the text.") - [Binary Tree Maximum Path Sum | 九章算法](http://www.jiuzhang.com/solutions/binary-tree-maximum-path-sum/)