美文网首页
124. Binary Tree Maximum Path Su

124. Binary Tree Maximum Path Su

作者: 衣介书生 | 来源:发表于2018-04-09 10:08 被阅读6次

    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; }
     * }
     */
    class Solution {
        private int res = Integer.MIN_VALUE;
        public int maxPathSum(TreeNode root) {
            helper(root);
            return res;
        }
        public int helper(TreeNode root) {                                                             
            if(root == null) return 0;
            int left = Math.max(helper(root.left), 0);
            int right = Math.max(helper(root.right), 0);
            res = Math.max(res, left + right + root.val);
            return Math.max(left, right) + root.val; 
        }
    }
    

    相关文章

      网友评论

          本文标题:124. Binary Tree Maximum Path Su

          本文链接:https://www.haomeiwen.com/subject/zgmbhftx.html