Maximum path sum in binary tree [handle any subtree, then handle the whole tree]

Preface

For binary trees , Make good use of its recursive constitution , Is the key to solving the problem , Handle any subtree in recursion , And you're done with the whole tree . Through the maximum path in the binary tree and practice backtracking + Dealing with subtrees .

One 、 Maximum path sum in binary tree

Two 、 to flash back + Dealing with subtrees

package everyday.hard;

//  The maximum path in a binary tree and .
public class MaxPathSum {
    
    /* target： Find any path and maximum value .  From the perspective of recursive structure , The left and right subtrees want to have paths , It must be that only one child can be selected from the left and right subtrees , Connect through parent node .  Choose the path value of the maximum sum , A variable can be used to record max that will do . */
    public int maxPathSum(TreeNode root) {
    
        //  Find the maximum value in the traversal process .
        order(root);
        //  Returns the maximum value found .
        return max;
    }

    private int max = 1 << 31;

    private int order(TreeNode root) {
    
        //  Access to the null node , Recursion ends , Return the contribution value 0.
        if (null == root) return 0;
        //  Backtracking   Left and right values .
        int left = order(root.left);
        int right = order(root.right);
        //  Four alternative paths , Left root  |  Right root  |  root  |  Left root right 
        //  The returned path and can only be the maximum of the first three , and max turn , You need to take the maximum of the four paths .
        //  Find out who is the biggest of the first three , Who is big , Return to who ; Then compare it with the left root and the right , Follow max Compare , obtain max.
        int rs = Math.max(left + root.val, Math.max(right + root.val, root.val));
        //  to update max
        max = Math.max(max, Math.max(rs, left + right + root.val));
        //  Returns the maximum subpath and 
        return rs;
    }

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

}

summary

1） Deal with each subtree .
2） Binary tree processing problem , Or from top to bottom , Or look at the problem from the bottom up .

reference

[1] LeetCode Maximum path sum in binary tree