Binary Tree Maximum Path Sum


  • 0
    S
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public int maxPathSum(TreeNode root) {
            Int maxSum = new Int(Integer.MIN_VALUE);
            getPathSumIncludingNode(root, maxSum);
            return maxSum.val;
        }
        
        private PathSum getPathSumIncludingNode(TreeNode node, Int maxSum){
            if(node == null) return null;
            
            if(node.left ==null && node.right ==null){
                maxSum.val = maxSum.val > node.val ?  maxSum.val : node.val;
                return new PathSum(node.val, node.val);
            }
            
            PathSum leftSubTree = getPathSumIncludingNode(node.left, maxSum);
            PathSum rightSubTree = getPathSumIncludingNode(node.right, maxSum);
            
            int bothSubTreeSum = (leftSubTree !=null ? leftSubTree.oneSubTreeSum : 0) + (rightSubTree != null ?rightSubTree.oneSubTreeSum : 0) + node.val ;
            int oneSubTreeSum = Math.max((leftSubTree !=null ? leftSubTree.oneSubTreeSum : 0), (rightSubTree != null ?rightSubTree.oneSubTreeSum : 0)) + node.val;
            oneSubTreeSum = oneSubTreeSum > node.val ? oneSubTreeSum : node.val; 
            maxSum.val = maxSum.val > Math.max(bothSubTreeSum, oneSubTreeSum) ?  maxSum.val : Math.max(bothSubTreeSum, oneSubTreeSum); 
            
            return new PathSum(bothSubTreeSum, oneSubTreeSum);
        }
        
        static class PathSum{
            int bothSubTreeSum;
            int oneSubTreeSum;
            public PathSum(int bothSubTreeSum, int oneSubTreeSum){
                this.bothSubTreeSum = bothSubTreeSum;
                this.oneSubTreeSum = oneSubTreeSum;
            }
        }
        
        static class Int{
            int val;
            public Int(int val){
                this.val = val;
            }
        }
    }
    

  • 0
    S
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        private int currentMax;
        public int maxPathSum(TreeNode root) {
            currentMax = root.val;
            maxPathSumUTIL(root);
            return currentMax;
        }
        
        public int maxPathSumUTIL(TreeNode root) {
            if(root == null) return 0;
            
            int leftMax = Math.max(0,maxPathSumUTIL(root.left));
            int rightMax = Math.max(0,maxPathSumUTIL(root.right));
            
            if(currentMax < (root.val + leftMax + rightMax))
                currentMax = root.val + leftMax + rightMax;
            return root.val + ((leftMax > rightMax)? leftMax : rightMax);
        }
    }
    

  • 0
    D

    Here is a solution in python.

    # Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    def pathSum(node):
        """
        Returns tuple with sum of longest path including node, and maximum path sum in subtree.
        """
        #      2
        #     / \    => returns (7, 11) which is 5+2 for the right side, and 4+2+5 for the subtree.
        #    4   5
        if node is None:
            return 0, None
        # check left and right sides.
        lsum, ltotal = pathSum(node.left)
        rsum, rtotal = pathSum(node.right)
        v = node.val
        # longest path going maybe left, through node, and maybe right.
        # either sides are optional since they may not contribute to increasing the value.
        path = max(0, lsum) + v + max(0, rsum)
        # maximum path sum for subtree, using 'or' to handle None.
        # it's either the longest path we just calculated, or one from a left/right subtree.
        total = max(path, ltotal or v, rtotal or v)
        # longest path through node, but going only on one side (path continued in parent).
        psum = v + max(0, lsum, rsum)
        return psum, total
    
    
    class Solution:
        def maxPathSum(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            psum, total = pathSum(root)
            return max(psum, total)
    

  • 0
    B

    using System;
    class BinarySearchTree
    {
    private int max = int.MinValue;
    Node root;
    public class Node
    {
    public int data;
    public Node right, left;
    public Node(int d)
    {
    data = d;
    right = null;
    left = null;
    }

    }
    
    public  int maxPathSum(Node root)
    {
        int rd = dfs(root);
        return rd > max ? rd : max;
    }
    private int dfs(Node root)
    {
        if (root.left == null && root.right == null)
        {
            return root.data;
        }
        if (root.left == null && root.right != null)
        {
            int roPathMax = dfs(root.right);
            max = roPathMax > max ? roPathMax : max;
            return Math.Max(root.data, roPathMax + root.data);
        }
        if (root.right == null && root.left != null)
        {
            int loPathMax = dfs(root.left);
            max = loPathMax > max ? loPathMax : max;
            return Math.Max(root.data, loPathMax + root.data);
        }
        int lPathMax = dfs(root.left);
        int rPathMax = dfs(root.right);
        int closePathMax = lPathMax + rPathMax + root.data;
    
        int innerMax = Math.Max(closePathMax, Math.Max(lPathMax, rPathMax));
        max = innerMax > max ? innerMax : max;
        return Math.Max(root.data, Math.Max(lPathMax + root.data, rPathMax + root.data));
    }
    static void Main()
    {
        BinarySearchTree BST = new BinarySearchTree();
        BST.Insert(0);
        BST.Insert(5);
        BST.Insert(-4);
        BST.Insert(-2);
        BST.Insert(7);
        BST.Insert(8);
        BST.Insert(6);
       //find max sum and  the subtree path
        Console.WriteLine("Max pathSum of the given binary tree is " + BST.maxPathSum(BST.root));
       
    
        Console.ReadKey();
    
    }
    
    public void Insert(int New)
    {
        Node N = new Node(New);
        if(root==null)
        {
            root = N;
        }
        else
        {
            Node current = root;
            Node parent;
            while(true)
            {
                parent = current;
                if(current.data > N.data)
                {
                    current = current.left;
                    if(current==null)
                    {
                        parent.left = N;
                        break;
                    }
                }
                else
                {
                    current = current.right;
                    if(current ==null)
                    {
                        parent.right = N;
                        break;
                    }
                }
            }
        }
    }
    

    }


  • 0
    G

    Clean Python Solution:

        class Solution(object):
          def maxPathSum(self, root):
          sums = []def dfs(root):
             if root.left and root.right:
                left = dfs(root.left)
                right = dfs(root.right)
                sums.append(root.val + left)
                sums.append(root.val + right)
                sums.append(root.val + left + right)
                sums.append(root.val)
                return max(root.val, root.val + left, root.val + right)
            elif root.left:
                left = dfs(root.left)
                sums.append(root.val + left)
                sums.append(root.val)
                return max(root.val, root.val + left)
            elif root.right:
                right = dfs(root.right)
                sums.append(root.val + right)
                sums.append(root.val)
                return max(root.val, root.val + right)
            else:
                sums.append(root.val)
                return root.val
          dfs(root)
          return max(sums)

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.