50 DSA-Questions: #33

#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;
    }
}