[알고리즘] 이 진 트 리 의 최대 경로 와

이 진 트 리 의 최대 경로 와
묘사 하 다.
비어 있 지 않 은 이 진 트 리 를 지정 하여 최대 경로 와.

  : [-10,9,20,null,null,15,7]

   -10
   / \
  9  20
    /  \
   15   7

  : 42

문제 풀이 의 사고 방향.
1. 모든 노드 에 대해 이 를 통과 하지만 부모 노드 를 통과 하지 않 는 가장 큰 경로 와.2. 전체 최대 경 로 는 모든 노드 결과 의 최대 값 입 니 다.

//     
    private int sum = Integer.MIN_VALUE;
    
    //              
    private int nodeValue(TreeNode node)
    {
        if (node == null) return 0;
        
        //     
        int leftValue = Math.max(nodeValue(node.left), 0);
        int rightValue = Math.max(nodeValue(node.right), 0);
        //              
        sum = Math.max(sum, node.val + leftValue + rightValue);
        return node.val + Math.max(leftValue, rightValue);
    }
    
        //   、     ：O(n)
    public int maxPathSum(TreeNode root)
    {
        return Math.max(this.nodeValue(root), sum);
    }