Subject to introduce

Force buckle 124 questions: leetcode-cn.com/problems/bi…

Analysis of the

Train of thought

  • When a path reaches a node, the following options are available: 1. Stop on the current node. 2. Go to the left child node. 3. Go to the right child node.
  • When you go to the child node and you have these three choices, recursion is good for dealing with the same problem of this size.
  • Notice, you don’t want to go into one branch and then go back to the other branch, because the paths overlap, which doesn’t work.

Define recursive functions

  • For a parent node, it cares about going into a child tree and getting the most out of it, but it doesn’t care how it goes.

  • Define the DFS function: Returns the maximum path sum that the current subtree can “provide” to the parent node. That is, a path that extends from the parent node will get the most out of the current subtree. There are three cases:

    1. The path stops at the root node of the current subtree. The maximum benefit of the current subtree is root.val 2. Val + DFS (root.left) 3 Root. val + Max (0, DFS (root.left), DFS (root.right))Copy the code

  • Note again: a path that extends from the parent node does not go to the left subtree and then back to the right subtree.

  • When traversing a null node, the null subtree provides no benefit and returns 0.

  • If the DFS of a subtree is negative, if we walk into it, the revenue will decrease instead of increasing. The subtree should be ignored, and we should not walk into it, and let it return 0 as if it were null.

The internal path in the subtree contains the root node

  • The maximum path sum is possible in one of the subtrees, as shown in the figure on the left.

  • So for each recursion of a subtree, find the sum of the maximum paths inside the current subtree, as shown in the green handwriting on the first right of the figure below, and compare the largest.

  • Note: the path inside a subtree contains the root node of the current subtree. If not, what is the path of the current subtree? It is the internal path of the current subtree.

  • So, the maximum sum of paths inside a subtree = the maximum sum of paths provided by the left subtree + the root node value + the maximum sum of paths provided by the right subtree. DFS (root.left) + root.val + DFS (root.right)

The code is as follows:.

/** * Definition for a binary tree node. * 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; *} *} */
class Solution {
    int result = Integer.MIN_VALUE;
    
    public int maxPathSum(TreeNode root) {
        dfs(root);
        return result;
    }

    // Returns the contribution of the current node to its parent
    public int  dfs(TreeNode root) {
        // If the current node is a leaf node, then the contribution to the parent node is 0
        if(root == null) {
            return 0;
        }
        // If it is not a leaf node, calculate the contribution of the left and right children of the current node
        int left = dfs(root.left);
        int right = dfs(root.right);
        // Update the maximum value, which is the current node value plus the contribution of the left and right nodes
        result = Math.max(result , root.val + left + right);
        // To calculate the maximum contribution the current node makes to the parent node, add val
        int max = Math.max(root.val + left , root.val + right);
        // If the contribution is less than 0, return 0
        return max < 0 ? 0: max; }}Copy the code

Time O(N), traversal of every node, space O(H), depth of recursion tree.