lintcode--94. 두 갈래 나무의 최대 경로와

2394 단어 LintCode

묘사


두 갈래 트리를 제시하고 경로와 최대를 찾을 수 있습니다. 경로는 어느 노드에서 시작하고 끝낼 수 있습니다. (경로와 두 노드 사이에 있는 경로의 노드 값의 합)

예제


두 갈래 나무 한 그루를 주시오.
       1
      / \
     2   3

되돌아오다

코드


뒷순서에 따라 아래에서 위로, max는 최대 값을 저장하고, maxPath 함수에서 좌우 트리의 어떤 하위 트리의 최대 값을 되돌려줍니다.
/**
 * 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
     */
    int max=Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        // write your code here
        if(root==null){
            return 0;
        }
        maxPath(root);
        return max;
    }
    private int maxPath(TreeNode root){
        if(root==null){
            return 0;
        }
        int left=maxPath(root.left);
        int right=maxPath(root.right);
        int cur=root.val+(left>0?left:0)+(right>0?right:0);
        max=Math.max(max,cur);
        return root.val+Math.max(left,right);
    }
}

좋은 웹페이지 즐겨찾기