📖
Coding problems
  • Overview
  • Second time
  • Third time
  • 2 sum
    • 2 sum?
    • 2 Sum All Pair I
    • 2 Sum All Pair II
    • 3 Sum
  • Array
    • Smallest and Largest
    • Largest and second largest
    • Longest Palindromic Substring
  • BFS
    • Array Hopper IV
    • Deep copy graph(possible loops)
    • Kth Smallest With Only 3, 5, 7 As Factors
    • Word Ladder
  • Binary Search
    • Closest in Sorted Array
    • Smallest Element that is larger than target
    • Search in unknown size array
  • Bit Operations
    • Basic Operations
    • Power of two?
    • Different bits
    • Reverse all bits of a number
    • Unique String
  • Deque
    • Deque with 3 stacks
    • Largest Rectangle in histogram
  • DFS Permutations
    • All subsets I
    • All subsets size k
    • Combinations For Telephone Pad I
    • Subsets of all permuations
    • Generate N valid parentheses I
    • Generate N valid parentheses II
    • Generate N valid parentheses III
    • Combinations of Coin
    • All Permutation String
    • All Permutations II
    • Telephone Combinations
  • Dynamic Programming
    • Array Hopper I
    • Array Hopper II
    • Array Hopper III
    • Cut Rope
    • Dictionary Word 1
    • Dictionary Word II
    • Eat Pizza
    • Largest Cross of Ones
    • Largest Square Surrounded By One
    • Largest X of 1s
    • Largest Square of Matches
    • Largest Submatrix Sum
    • Longest Ascending Subsequence I & II
    • Longest Common Sequence between two strings
    • Most with positive slope
    • Palindrome Partition
    • Edit Distance
    • Square of ones
    • Wild card matching
    • Wood Cutting
    • 188. Best Time to Buy and Sell Stock IV
  • Graph Search
    • Kth closest to <0, 0, 0>
    • Largest Product of Length
  • HashTable
    • Top K frequent words
    • Bipartite
  • Heap
  • LinkedList
    • Reverse
    • Merge Sort Linked List
    • Re-Order LinkedList
  • Slow fast pointers
    • Remove duplicate elements in array
  • Problem Solving
    • Water Level I
    • Largest rectangle in histogram
    • Range Addition II
  • Recursion
    • ReverseTree
    • NQueen
    • NQueen optimized
    • Spiral Order Print I
    • Spiral Order Print II
    • String Abbreviation Matching
  • Sliding Window
    • Longest subarray contains only 1s
    • Longest Substring Without Repeating Characters
    • Maximum Number within Window
  • Sorts
    • QuickSort
  • String
    • All Anagrams
    • is substring of string
    • Reverse String
    • Reverse Words on sentence
    • Remove Chars from String in place
    • Right shift N characters
    • Remove Leading/duplicate/trailing spaces
    • Shuffle String
    • String Abbreviation Matching
  • Tree Traversal
    • Check balanced tree
    • Check if complete tree
    • Delete in binary tree
    • LCA of two tree nodes
    • Get Keys In Binary Search Tree In Given Range
    • Height of Tree
    • Symmetric Tree?
    • Tweaked Binary tree
    • Set left node count
    • Greatest difference Left and Right subtree count Node
    • Largest Number Smaller in BST
    • Closest Number in Binary Search Tree II
    • Max Path Sum From Leaf To Root
    • Maximum Path Sum Binary Tree I
    • Maximum Path Sum Binary Tree II
    • Maximum Path Sum Binary Tree III
    • Flatten Binary Tree to Linked List
    • Iterative Post-Order Traversal
  • Unsorted Array
    • Find missing number
Powered by GitBook
On this page

Was this helpful?

  1. Tree Traversal

Maximum Path Sum Binary Tree I

Medium

Given a binary tree in which each node contains an integer number. Find the maximum possible sum from one leaf node to another leaf node. If there is no such path available, return Integer.MIN_VALUE(Java)/INT_MIN (C++).

Examples

-15

/ \

2 11

/ \

6 14

The maximum path sum is 6 + 11 + 14 = 31.

Solution:

To Parent: return root.key + max(left path, right path)

At Current: update globalMax against root.key + left path + right path

From Children: largest sum left path and largest sum right path

public class Solution {
  public int maxPathSum(TreeNode root) {
    int[] max = new int[]{Integer.MIN_VALUE};
    helper(root, max);
    return max[0];
  }

  private int helper(TreeNode root, int[] max){
    if (root == null){
      return 0;
    }

    if (root.right == null && root.left == null) {
      return root.key;
    } else if (root.right == null) {
      return helper(root.left, max) + root.key;
    } else if (root.left == null) {
      return helper(root.right, max) + root.key;
    } else {
      //case 4
      // from children
      // get best partial paths from left and right
      int bestLPath = helper(root.left, max);
      int bestRPath = helper(root.right, max);

      // at current
      // compare completeLocalPath to global maximum path
      int completeLocalPath = bestLPath + root.key + bestRPath;
      max[0] = Math.max(max[0], completeLocalPath);

      // to parent
      // pass up best partial path
      return Math.max(bestLPath, bestRPath) + root.key;
    }
  }
}

Mistakes Made:

problem constraint states a valid path must be from one leaf node to another. This means that we can only update the global maximum if we have both a left and right child

PreviousMax Path Sum From Leaf To RootNextMaximum Path Sum Binary Tree II

Last updated 4 years ago

Was this helpful?