Java Post-order Traversal Easy Solution


  • 0
    V
    In this simple solution, post-order traversal is done. 
    Once a node is visited, sum = maxLeft + root.val + maxRight; and it is compared with global maxPath.
    Value returned at each node is max(0, maxLeft + root.val, root.val + maxRight). 
    To maximize the maxPath, parent can visit either left or right sub-tree of its child if one of them is greater than 0.
    
    
    int maxPath = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        maxPathHelper(root);
        return maxPath;
    }
    
    int maxPathHelper(TreeNode root) {
        if(root == null)
            return 0;
        int maxLeft = maxPathHelper(root.left);
        int maxRight = maxPathHelper(root.right);
        int sum = maxLeft + root.val + maxRight;
        if(sum > maxPath)
            maxPath = sum;
        return Math.max(0, Math.max(maxLeft + root.val, root.val + maxRight));
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.