fork download
copy 
  1. public class Main {
  2.  
  3.     static class TreeNode {
  4.         int val;
  5.         TreeNode left, right;
  6.  
  7.         TreeNode(int val) {
  8.             this.val = val;
  9.         }
  10.     }
  11.  
  12.     /*
  13.      * normal:
  14.      * Bina zero operation ke current node se neeche
  15.      * jaane wale maximum path ka sum.
  16.      *
  17.      * modified:
  18.      * At most ek node ko 0 karke current node se neeche
  19.      * jaane wale maximum path ka sum.
  20.      */
  21.     static class State {
  22.         long normal;
  23.         long modified;
  24.  
  25.         State(long normal, long modified) {
  26.             this.normal = normal;
  27.             this.modified = modified;
  28.         }
  29.     }
  30.  
  31.     static long ans;
  32.  
  33.     public static long maxPathSum(TreeNode root) {
  34.  
  35.         ans = Long.MIN_VALUE;
  36.  
  37.         dfs(root);
  38.  
  39.         return ans;
  40.     }
  41.  
  42.     private static State dfs(TreeNode root) {
  43.  
  44.         if (root == null) {
  45.             return new State(
  46.                 Long.MIN_VALUE / 4,
  47.                 Long.MIN_VALUE / 4
  48.             );
  49.         }
  50.  
  51.         State left = dfs(root.left);
  52.         State right = dfs(root.right);
  53.  
  54.         /*
  55.          * Negative child ko path mein lena compulsory nahi hai.
  56.          *
  57.          * Isliye negative contribution ko 0 kar dete hain.
  58.          */
  59.         long leftNormal = Math.max(0L, left.normal);
  60.         long rightNormal = Math.max(0L, right.normal);
  61.  
  62.  
  63.         // =====================================================
  64.         // STATE 1: Bina zero operation ke downward path
  65.         // =====================================================
  66.  
  67.         /*
  68.          * Current node se parent ki taraf return karte waqt
  69.          * sirf ONE child choose kar sakte hain.
  70.          *
  71.          * root
  72.          *  / \
  73.          * L   R
  74.          *
  75.          * Path:
  76.          * root -> L
  77.          * OR
  78.          * root -> R
  79.          */
  80.         long normal =
  81.                 root.val + Math.max(leftNormal, rightNormal);
  82.  
  83.  
  84.         // =====================================================
  85.         // STATE 2: At most one node ko zero karne ke baad
  86.         // downward path
  87.         // =====================================================
  88.  
  89.         /*
  90.          * CASE 1:
  91.          * Current node ko 0 kar diya.
  92.          *
  93.          * IMPORTANT:
  94.          * Yahan bhi sirf ONE child le sakte hain,
  95.          * because ye value parent ko return hogi.
  96.          *
  97.          *  L
  98.          *  |
  99.          *  0
  100.          *
  101.          * OR
  102.          *
  103.          *  0
  104.          *   |
  105.          *   R
  106.          */
  107.         long modifyCurrent =
  108.                 Math.max(leftNormal, rightNormal);
  109.  
  110.  
  111.         /*
  112.          * CASE 2:
  113.          * Zero operation left subtree mein use hua.
  114.          *
  115.          * Current node normal rahega.
  116.          */
  117.         long modifyLeft =
  118.                 root.val + left.modified;
  119.  
  120.  
  121.         /*
  122.          * CASE 3:
  123.          * Zero operation right subtree mein use hua.
  124.          */
  125.         long modifyRight =
  126.                 root.val + right.modified;
  127.  
  128.  
  129.         /*
  130.          * "At most one" ka matlab:
  131.          * zero operation use na karna bhi allowed hai.
  132.          */
  133.         long modified =
  134.                 Math.max(
  135.                     normal,
  136.                     Math.max(
  137.                         modifyCurrent,
  138.                         Math.max(modifyLeft, modifyRight)
  139.                     )
  140.                 );
  141.  
  142.  
  143.         // =====================================================
  144.         // COMPLETE PATH CASES
  145.         // =====================================================
  146.  
  147.         /*
  148.          * Ab hum parent ko value return nahi kar rahe.
  149.          *
  150.          * Yahan complete path ban sakta hai:
  151.          *
  152.          *       L
  153.          *        \
  154.          *         root
  155.          *        /
  156.          *       R
  157.          *
  158.          * Isliye LEFT + ROOT + RIGHT allowed hai.
  159.          */
  160.  
  161.         // CASE 1: Normal complete path
  162.         long normalThrough =
  163.                 leftNormal +
  164.                 root.val +
  165.                 rightNormal;
  166.  
  167.  
  168.         // CASE 2: Current node ko zero kar diya
  169.         long specialAtCurrent =
  170.                 leftNormal +
  171.                 rightNormal;
  172.  
  173.  
  174.         // CASE 3: Zero left subtree mein hai
  175.         long specialInLeft =
  176.                 left.modified +
  177.                 root.val +
  178.                 rightNormal;
  179.  
  180.  
  181.         // CASE 4: Zero right subtree mein hai
  182.         long specialInRight =
  183.                 leftNormal +
  184.                 root.val +
  185.                 right.modified;
  186.  
  187.  
  188.         // Global answer update
  189.         ans = Math.max(ans, normalThrough);
  190.         ans = Math.max(ans, specialAtCurrent);
  191.         ans = Math.max(ans, specialInLeft);
  192.         ans = Math.max(ans, specialInRight);
  193.  
  194.  
  195.         /*
  196.          * Parent ko sirf downward path return karna hai.
  197.          *
  198.          * Complete path return nahi kar sakte,
  199.          * because parent usko further extend nahi kar sakta.
  200.          */
  201.         return new State(normal, modified);
  202.     }
  203.  
  204.  
  205.     public static void main(String[] args) {
  206.  
  207.         /*
  208.                  5
  209.                /   \
  210.             -50     5
  211.             /  \
  212.            5    5
  213.  
  214.         Zero operation:
  215.         -50 -> 0
  216.  
  217.         Best path:
  218.  
  219.         5 -> 0 -> 5 -> 5
  220.  
  221.         Sum = 5 + 0 + 5 + 5
  222.             = 15
  223.         */
  224.  
  225.         TreeNode root = new TreeNode(5);
  226.  
  227.         root.left = new TreeNode(-50);
  228.         root.right = new TreeNode(5);
  229.  
  230.         root.left.left = new TreeNode(5);
  231.         root.left.right = new TreeNode(5);
  232.  
  233.         System.out.println(maxPathSum(root));
  234.     }
  235. }
Success #stdin #stdout 0.08s 52560KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
15
https://ideone.com/eAGZtJ
language:
Java (HotSpot 12)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!