/
githubmirror
/
interviews
Обзор
Документация
Войти
/
githubmirror
/
interviews
Код
Запросы
0
Пакеты
0
Релизы
0
Аналитика
Безопасность
master
leetcode/tree/BinaryTreeMaximumPathSum.java
42 строки
1 KB
Kevin Naughton Jr
finish renaming files and directories
27 мар 2018, 19:52
27 мар 2018, 19:52
ec6dfb5
Код
Авторство
О чём код?
// Given a binary tree, find the maximum path sum. // For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root. // For example: // Given the below binary tree, // 1 // / \ // 2 3 // Return 6. /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class BinaryTreeMaximumPathSum { int max = Integer.MIN_VALUE; public int maxPathSum(TreeNode root) { maxPathSumRecursive(root); return max; } private int maxPathSumRecursive(TreeNode root) { if(root == null) { return 0; } int left = Math.max(maxPathSumRecursive(root.left), 0); int right = Math.max(maxPathSumRecursive(root.right), 0); max = Math.max(max, root.val + left + right); return root.val + Math.max(left, right); } }