[LeetCode-124] Binary Tree Maximum Path Sum-白红宇

[LeetCode-124] Binary Tree Maximum Path Sum

阅读量：5307 次

发布时间：2019-06-14

本文共 1751 字，大约阅读时间需要 5 分钟。

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.

二叉树后序历遍的变形。

1 /** 2  * Definition for binary tree 3  * struct TreeNode { 4  *     int val; 5  *     TreeNode *left; 6  *     TreeNode *right; 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8  * }; 9  */10 class Solution {11 public:12     int result;13     inline bool has_left(TreeNode *root) {14         return NULL != root->left;15     }16     inline bool has_right(TreeNode *root) {17         return NULL != root->right;18     }19     void trace_last(TreeNode *pnode) {20         int tmpv = pnode->val, tmplv = pnode->val, tmprv = pnode->val, tmpresult = -INT_MAX;21         if (has_left(pnode)) {22             trace_last(pnode->left);23             tmplv = max
      
       (tmpv, pnode->val + pnode->left->val);24         }25         if (has_right(pnode)) {26             trace_last(pnode->right);27             tmprv = max
       
        (tmpv, pnode->val + pnode->right->val);28         }29         tmpresult = max
        
         (max
         
          (tmpv, tmplv + tmprv - tmpv), max
          
           (tmplv, tmprv));30         if (tmpresult > result) {31             result = tmpresult;32         }33         pnode->val = max
           
            (max
            
             (tmplv, tmprv), tmpv);34 }35 int maxPathSum(TreeNode *root) {36 // Start typing your C/C++ solution below37 // DO NOT write int main() function38 result = -INT_MAX;39 trace_last(root);40 return result;41 }42 };