Binary Tree Maximum Path Sum II (Ladder)

Description

Given a binary tree, find the maximum path sum from root. The path may end at any node in the tree and contain at least one node in it.

Example
Given the below binary tree:

  1
 / \
2   3

return 4. (1->3)

Link

Lintcode_ladder

Method

1. x
2. x

Example

1. 1

   /**
   * 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 maxPathSum2(TreeNode *root) {
        // Write your code here
        if (!root) {
            return 0;
        }
        // return max(0, max(maxPathSum2(root->left), maxPathSum2(root->right))) + root->val;
        int left = max(0, maxPathSum2(root->left));
        int right = max(0, maxPathSum2(root->right));
        return max(left, right) + root->val; 
    }
   };
   

Similar problems

x

Tags

x