#33. Binary Tree Maximum Path Sum
A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root. The path sum of a path is the sum of the node's values in the path. Given the root of a binary tree, return the maximum path sum of any non-empty path.
Soluția mea țărănească:
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
int getVal() {
return val;
}
TreeNode getLeft() {
return left;
}
TreeNode getRight() {
return right;
}
}
class Solution {
public int maxPathSum(TreeNode root) {
Map<Integer, NodeInfo> nodes = new HashMap<>();
calculateMax(root, 0, nodes);
int max = Integer.MIN_VALUE;
for (NodeInfo node : nodes.values()) {
if (max < node.getMaxSumComplete()) {
max = node.getMaxSumComplete();
}
if (max < node.getMaxSumIncomplete()) {
max = node.getMaxSumIncomplete();
}
}
return max;
}
private void calculateMax(TreeNode currentNode, int index, Map<Integer, NodeInfo> nodesInfo) {
if (currentNode.getLeft() == null && currentNode.getRight() == null) {
NodeInfo nodeInfo = new NodeInfo(index, currentNode.getVal(), currentNode.getVal());
nodesInfo.put(index, nodeInfo);
return ;
}
int maxIncompleteLeft = 0;
if (currentNode.getLeft() != null) {
calculateMax(currentNode.getLeft(), 2 * index + 1, nodesInfo);
maxIncompleteLeft = nodesInfo.get(2 * index + 1).getMaxSumIncomplete();
}
int maxIncompleteRight = 0;
if (currentNode.getRight() != null) {
calculateMax(currentNode.getRight(), 2 * index + 2, nodesInfo);
maxIncompleteRight = nodesInfo.get(2 * index + 2).getMaxSumIncomplete();
}
int maxComplete = maxIncompleteLeft + currentNode.getVal() + maxIncompleteRight;
int maxIncomplete = Math.max(Math.max(maxIncompleteLeft, maxIncompleteRight), 0) + currentNode.getVal();
NodeInfo nodeInfo = new NodeInfo(index, maxComplete, maxIncomplete);
nodesInfo.put(index, nodeInfo);
}
class NodeInfo {
int index;
int maxSumComplete;
int maxSumIncomplete;
public NodeInfo(int index, int maxSumComplete, int maxSumIncomplete) {
this.index = index;
this.maxSumComplete = maxSumComplete;
this.maxSumIncomplete = maxSumIncomplete;
}
public int getIndex() {
return index;
}
public int getMaxSumComplete() {
return maxSumComplete;
}
public int getMaxSumIncomplete() {
return maxSumIncomplete;
}
}
}
O soluție super eficientă (leetcode):
class Solution {
int sum = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
maxSum(root);
return sum;
}
int maxSum(TreeNode node) {
if(node == null) {
return 0;
}
int left = maxSum(node.left);
int right = maxSum(node.right);
int ret = Integer.max(node.val, node.val + Integer.max(left, right));
sum = Integer.max(sum, Integer.max(ret, node.val + left + right));
return ret;
}
}
Niciun comentariu:
Trimiteți un comentariu