Leetcode discuss: 124. Binary Tree Maximum Path Sum

July 10, 2021

Here is the link. 

C# | Post order traversal | Bottom up | One visit each node | Optimal time and space

July 10, 2021
Introduction
It takes time for me to finish all tree algorithms, easy medium and hard level. I did complete the project in 2020. Now there are another 50 tree algorithms, and I like to spend time to work on. But I learned better through onsite interview, specially when I made mistake not to provide optimal time complexity this May, 2021.

Bottom up | Post order traversal | Each node has 4 values
Most of important is to make it simple. One visit of each node in the tree using bottom- up post order traversal is good enough to solve all calculation need.

Cross root maximum path | root to leaf node path maximum sum
There are four cases for cross root maximum path sum, left subtree take it or leave it, same as right subtree.

There are three cases for root to leaf node path maximum sum, root value itself, + left subtree's max, + right subtree's max.

The following code passes online judge.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    
    /// <summary>
    /// July 10, 2021
    /// Apply post order traversal once, bottom up, each node
    /// is visited only once, and each node will calculate root node
    /// to leaf node's max path, cross root node maximum path. 
    /// Space optimal: O(1)
    /// Time complexity: O(N)
    /// Each node has four values:
    /// 1. Node value itself
    /// 2. Node + left subtree
    /// 3. Node + right subtree
    /// 4. Cross root node max path
    /// </summary>
    /// <param name="root"></param>
    /// <returns></returns>
    public int MaxPathSum(TreeNode root)
    {
        if(root == null)
        {
            return 0; 
        }

        var maxCrossRoot = Int32.MinValue;

        applyPostOrderTraversal(root, ref maxCrossRoot);
        
        return maxCrossRoot; 
    }

    /// <summary>
    /// post order - L, R, Root
    /// Calculate root node to leaf node max path sum - return value
    /// Each node has four values to compare
    /// </summary>
    /// <param name="root"></param>
    /// <param name="maxCrossRoot"></param>
    /// <returns></returns>
    private int applyPostOrderTraversal(TreeNode root, ref int maxCrossRoot)
    {
        if(root == null)
        {
            return 0; 
        }

        var left = applyPostOrderTraversal(root.left, ref maxCrossRoot);
        var right = applyPostOrderTraversal(root.right, ref maxCrossRoot);

        var value = root.val;
        var current = value; 
        if(left > 0)
        {
            current += left;
        }

        if (right > 0)
        {
            current += right; 
        }

        maxCrossRoot = Math.Max(maxCrossRoot, current);

        var toLeaf = new int[] { value, value + left, value + right };
        return toLeaf.Max(); 
    }
}