Binary Tree Maximum Path Sum(이 진 트 리 의 최대 경로 와)

http://www.lintcode.com/en/problem/binary-tree-maximum-path-sum/?rand=true
/**
 * Definition of TreeNode:
 * public class TreeNode {
 * public int val;
 * public TreeNode left, right;
 * public TreeNode(int val) {
 * this.val = val;
 * this.left = this.right = null;
 * }
 * }
 */
public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: An integer.
     */
    public int maxPathSum(TreeNode root) {
        // write your code here
        return tree(root).maxPath;
    }

    private Node tree(TreeNode root) {
        Node node = new Node(0, Integer.MIN_VALUE);
        if (root == null) {
            return node;
        }
        Node left = tree(root.left);
        Node right = tree(root.right);
//        singlePath        ,        ,              ,
        node.singlePath = Math.max(node.singlePath, Math.max(left.singlePath, right.singlePath) + root.val);
//        maxPath           ,            
        node.maxPath = Math.max(Math.max(left.maxPath, right.maxPath), left.singlePath + right.singlePath + root.val);
        return node;
    }

    private class Node {
        //          
        int singlePath;
        //           
        int maxPath;

        public Node(int singlePath, int maxPath) {
            this.singlePath = singlePath;
            this.maxPath = maxPath;
        }
    }
}

좋은 웹페이지 즐겨찾기