package trees.leetcode;
import java.util.ArrayList;
import java.util.List;
public class MaximumSumPath {
int val;
val = x;
}
}
static List<Integer> path;
static int sum = 0;
public List
<Integer
> maxPathSum
(TreeNode root
) { if ( root == null)
return new ArrayList<>();
maxPathSumUtil(root);
return path;
}
private List
<Integer
> maxPathSumUtil
(TreeNode root
) { if ( root == null)
return new ArrayList<>();
List<Integer> currRoot = new ArrayList<>();
List<Integer> leftTree = maxPathSumUtil(root.left);
int leftTreeSum
= Math.
max(0, leftTree.
stream().
mapToInt(l
-> l
).
sum()); int currSum = leftTreeSum;
if ( leftTreeSum > 0)
currRoot.addAll(leftTree);
currSum += root.val;
currRoot.add(root.val);
List<Integer> rightTree = maxPathSumUtil(root.right);
int rightTreeSum
= Math.
max(0, rightTree.
stream().
mapToInt( l
-> l
).
sum()); currSum += rightTreeSum;
if ( rightTreeSum > 0)
currRoot.addAll(rightTree);
if ( currSum > sum) {
path = new ArrayList<>();
path.addAll(currRoot);
sum = currSum;
}
if ( leftTreeSum > rightTreeSum) {
currRoot.removeAll(rightTree);
}
else if ( rightTreeSum > leftTreeSum) {
currRoot.removeAll(leftTree);
}
return currRoot;
}
public static void main
(String args
[]) { root.
left.
left.
left = new TreeNode(100); root.
left.
left.
right = new TreeNode(101);
new MaximumSumPath
().
maxPathSum(root
).
forEach( t
-> System.
out.
print( t
+ " ")); }
}
cGFja2FnZSB0cmVlcy5sZWV0Y29kZTsKCmltcG9ydCBqYXZhLnV0aWwuQXJyYXlMaXN0OwppbXBvcnQgamF2YS51dGlsLkxpc3Q7CgpwdWJsaWMgY2xhc3MgTWF4aW11bVN1bVBhdGggewoKICAgIHB1YmxpYyBzdGF0aWMgY2xhc3MgVHJlZU5vZGUgewogICAgICAgIGludCB2YWw7CiAgICAgICAgVHJlZU5vZGUgbGVmdDsKICAgICAgICBUcmVlTm9kZSByaWdodDsKCiAgICAgICAgVHJlZU5vZGUoaW50IHgpIHsKICAgICAgICAgICAgdmFsID0geDsKICAgICAgICB9CiAgICB9CiAgICBzdGF0aWMgTGlzdDxJbnRlZ2VyPiBwYXRoOwogICAgc3RhdGljIGludCBzdW0gPSAwOwogICAgcHVibGljIExpc3Q8SW50ZWdlcj4gbWF4UGF0aFN1bShUcmVlTm9kZSByb290KSB7CiAgICAgICAgaWYgKCByb290ID09IG51bGwpCiAgICAgICAgICAgIHJldHVybiBuZXcgQXJyYXlMaXN0PD4oKTsKCiAgICAgICAgc3VtID0gSW50ZWdlci5NSU5fVkFMVUU7CgogICAgICAgIG1heFBhdGhTdW1VdGlsKHJvb3QpOwogICAgICAgIHJldHVybiBwYXRoOwoKICAgIH0KCiAgICBwcml2YXRlIExpc3Q8SW50ZWdlcj4gbWF4UGF0aFN1bVV0aWwoVHJlZU5vZGUgcm9vdCkgICB7CiAgICAgICAgaWYgKCByb290ID09IG51bGwpCiAgICAgICAgICAgIHJldHVybiBuZXcgQXJyYXlMaXN0PD4oKTsKCiAgICAgICAgTGlzdDxJbnRlZ2VyPiBjdXJyUm9vdCA9IG5ldyBBcnJheUxpc3Q8PigpOwogICAgICAgIExpc3Q8SW50ZWdlcj4gbGVmdFRyZWUgPSBtYXhQYXRoU3VtVXRpbChyb290LmxlZnQpOwoKICAgICAgICBpbnQgbGVmdFRyZWVTdW0gPSBNYXRoLm1heCgwLCBsZWZ0VHJlZS5zdHJlYW0oKS5tYXBUb0ludChsIC0+IGwpLnN1bSgpKTsKICAgICAgICBpbnQgY3VyclN1bSA9IGxlZnRUcmVlU3VtOwogICAgICAgIGlmICggbGVmdFRyZWVTdW0gPiAwKQogICAgICAgICAgICBjdXJyUm9vdC5hZGRBbGwobGVmdFRyZWUpOwoKICAgICAgICBjdXJyU3VtICs9IHJvb3QudmFsOwogICAgICAgIGN1cnJSb290LmFkZChyb290LnZhbCk7CgogICAgICAgIExpc3Q8SW50ZWdlcj4gcmlnaHRUcmVlID0gbWF4UGF0aFN1bVV0aWwocm9vdC5yaWdodCk7CiAgICAgICAgaW50IHJpZ2h0VHJlZVN1bSA9IE1hdGgubWF4KDAsIHJpZ2h0VHJlZS5zdHJlYW0oKS5tYXBUb0ludCggbCAtPiBsICkuc3VtKCkpOwogICAgICAgIGN1cnJTdW0gKz0gcmlnaHRUcmVlU3VtOwogICAgICAgIGlmICggcmlnaHRUcmVlU3VtID4gMCkKICAgICAgICAgICAgY3VyclJvb3QuYWRkQWxsKHJpZ2h0VHJlZSk7CgogICAgICAgIGlmICggY3VyclN1bSA+IHN1bSkgewogICAgICAgICAgICBwYXRoID0gbmV3IEFycmF5TGlzdDw+KCk7CiAgICAgICAgICAgIHBhdGguYWRkQWxsKGN1cnJSb290KTsKICAgICAgICAgICAgc3VtID0gY3VyclN1bTsKICAgICAgICB9CgogICAgICAgIGlmICggbGVmdFRyZWVTdW0gPiByaWdodFRyZWVTdW0pICAgIHsKICAgICAgICAgICAgY3VyclJvb3QucmVtb3ZlQWxsKHJpZ2h0VHJlZSk7CiAgICAgICAgfQogICAgICAgIGVsc2UgaWYgKCByaWdodFRyZWVTdW0gPiBsZWZ0VHJlZVN1bSkgICB7CiAgICAgICAgICAgIGN1cnJSb290LnJlbW92ZUFsbChsZWZ0VHJlZSk7CiAgICAgICAgfQoKICAgICAgICByZXR1cm4gY3VyclJvb3Q7CiAgICB9CgogICAgcHVibGljIHN0YXRpYyB2b2lkIG1haW4oU3RyaW5nIGFyZ3NbXSkgIHsKICAgICAgICBUcmVlTm9kZSByb290ID0gbmV3IFRyZWVOb2RlKC0xKTsKICAgICAgICByb290LmxlZnQgPSBuZXcgVHJlZU5vZGUoLTIpOwogICAgICAgIHJvb3QubGVmdC5sZWZ0ID0gbmV3IFRyZWVOb2RlKDMpOwogICAgICAgIHJvb3QubGVmdC5sZWZ0LmxlZnQgPSBuZXcgVHJlZU5vZGUoMTAwKTsKICAgICAgICByb290LmxlZnQubGVmdC5yaWdodCA9IG5ldyBUcmVlTm9kZSgxMDEpOwogICAgICAgIHJvb3QucmlnaHQgPSBuZXcgVHJlZU5vZGUoMyk7CiAgICAgICAgcm9vdC5yaWdodC5sZWZ0ID0gbmV3IFRyZWVOb2RlKDQpOwogICAgICAgIHJvb3QucmlnaHQucmlnaHQgPSBuZXcgVHJlZU5vZGUoNyk7CgogICAgICAgIG5ldyBNYXhpbXVtU3VtUGF0aCgpLm1heFBhdGhTdW0ocm9vdCkuZm9yRWFjaCggdCAtPiBTeXN0ZW0ub3V0LnByaW50KCB0ICArICIgIikpOwogICAgfQoKfQo=