8 lines Python and a shortest 5 lines python for fun


  • 1

    Regular one:

    class Solution(object):
        def maxPathSum(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            self.sum = root.val
            def dfs(root):
                if not root: return 0
                l = dfs(root.left)
                r = dfs(root.right)
                self.sum = max(self.sum, root.val + max(l, r), root.val, root.val + l + r)
                return max(root.val, root.val + max(l, r))
            return max(dfs(root), self.sum)
    

    Shortest one:

    class Solution(object):
        def maxPathSum(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            def dfs(root):
                if not root: return (0, float("-inf"))
                (l, lm), (r, rm) = map(dfs, [root.left, root.right])
                return (max(root.val, root.val + max(l, r)), max(lm, rm, root.val + max(l, r), root.val, root.val + l + r))
            return dfs(root)[1]
    

  • 1

    zhen-five line

    public class Solution {
        public int maxPathSum(TreeNode root) {
            result = Integer.MIN_VALUE;
            
            search(root);
            
            return result;
        }
        
        private int search(TreeNode node) {
            if (node == null) return 0;
            
            int leftResult = search(node.left);
            int rightResult = search(node.right);
            
            result = Math.max(Math.max(Math.max(Math.max(leftResult, rightResult) + node.val, node.val), leftResult + rightResult + node.val), result);
            
            return Math.max(Math.max(leftResult, rightResult), 0) + node.val;
        }
        
        private int result;
    }
    

  • 0

    @adam47 This is obviously 13 lines. Did you seriously count it?


  • 0
    This post is deleted!

  • 1

    @jedihy What are you talking about?


Log in to reply
 

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