Hello, everyone, I am the beaten Amumu, love algorithm front-end fish old. Recently, I will frequently share with you my thoughts and experiences in the process of brush algorithm. If you also want to improve the forced case of fish old, welcome to pay attention to me, learn together.

The title

124. Maximum path sum in binary trees

A path is defined as a sequence that starts at any node in the tree and follows parent to child nodes to reach any node. The same node appears at most once in a path sequence. The path contains at least one node and does not necessarily go through the root node.

Path and is the sum of the values of all nodes in a path.

Give you the root node of a binary tree, root, return its maximum path and.

 

Example 1:

Input: root = [1,2,3] Output: 6 Description: The optimal path is 2 -> 1 -> 3, and the sum of paths is 2 + 1 + 3 = 6Copy the code

Example 2:

Input: root = [-10,9,20, NULL, NULL,15,7] Output: 42 Description: The optimal path is 15 -> 20 -> 7, and the sum of paths is 15 + 20 + 7 = 42Copy the code

 

Tip:

  • The number of nodes in the tree ranges from[1, 3 * 104]
  • -1000 <= Node.val <= 1000

Train of thought

To find the maximum path sum: can be converted into a recursive problem, first of all, the maximum path sum either exists in the root node, or there is a left subtree of the root node, that is, the left node, or there is a left subtree, that is, the right node, only these three cases, we can recurse layers down. However, since the sum of paths is required, we have to find the longest path of each node first and record it with map, which is the prefix sum, and then recursively find the maximum path sum through the second traversal.

  1. First find the maximum path sum of each node, take the maximum sum of left and right nodes plus the value of the current node;
  2. Walk through the tree again, comparing each node in three ways: take left, take right, or take middle;
  3. Form a recursive problem, the recursive transfer equation is to solve the maximum value of the current node is divided into three parts for comparison.

implementation

/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */
/ * * *@param {TreeNode} root
 * @return {number}* /
var maxPathSum = function(root) {
    if(! root)return 0;
    let map = getPathMap(root);

    function getPathSum(node) {
        if(! node)return 0;

        let leftValue = Math.max((map.get(node.left) || 0), 0);
        let rightValue = Math.max((map.get(node.right) || 0), 0);

        // The maximum value of the current node is equal to the maximum value of the left and right nodes plus the current value
        let cur = node.val + leftValue + rightValue;

        let compareList = [ cur ];
        node.left && compareList.push(getPathSum(node.left));
        node.right && compareList.push(getPathSum(node.right));

        return Math.max(... compareList); }return getPathSum(root, map);
};

// Find the path prefix and for each node
function getPathMap(root) {
    let map = new Map(a);// Find the maximum single path for each node,
    const getMaxPath = (node) = > {
        if(! node)return 0;

        const maxSubValue = Math.max(getMaxPath(node.left), getMaxPath(node.right));
        const maxValue = maxSubValue > 0 ? node.val + maxSubValue : node.val;
        map.set(node, maxValue);

        return maxValue;
    }

    getMaxPath(root);

    return map;
}   
Copy the code

To optimize the

  1. We found that top-down recursion needed to be usedmapSave the value once and go through two rounds of recursion at the same time to find the corresponding result;
  2. But bottom-up recursion is not, you can get the longest path and directly record the maximum value externally.

Optimize the code

/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */
/ * * *@param {TreeNode} root
 * @return {number}* /
var maxPathSum = function(root) {
    if(! root)return 0;

    let maxValue = Number.MIN_SAFE_INTEGER;

    // Find the maximum single path for each node
    const getMaxPath = (node) = > {
        if(! node)return 0;

        // Find the child node
        // If the node path is negative, we do not add it, as if there is no node
        const leftValue = Math.max(getMaxPath(node.left), 0);
        const rightValue = Math.max(getMaxPath(node.right), 0);

        // Record the total path and maximum value
        maxValue = Math.max(maxValue, node.val + leftValue + rightValue);

        return Math.max(leftValue, rightValue) + node.val;
    }

    getMaxPath(root);

    return maxValue;
};

 
Copy the code

If you understand it, you can click on it and see you in the next topic. If there is no accident after the article will be in this form, there are good suggestions welcome to comment area.