94. 두 갈래 트리의 최대 경로 및 (동적 계획)

묘사

두 갈래 트리를 제시하고 경로와 최대를 찾을 수 있습니다. 경로는 어느 노드에서 시작하고 끝낼 수 있습니다. (경로와 두 노드 사이에 있는 경로의 노드 값의 합)
당신은 실제 면접에서 이 문제를 만난 적이 있습니까?  
예.

예제

두 갈래 나무 한 그루를 주시오.

       1
      / \
     2   3

복귀 6이 두 갈래 나무의 가장 큰 경로를 구하는 것은 매우 어려운 문제이다. 어려우면 시작 위치와 끝 위치에서 임의의 위치가 될 수 있다. 나는 당연히 할 줄 모른다. 그래서 인터넷에 접속해서 신들의 해법을 본다. 이런 비슷한 수의 반복적인 문제는 일반적으로 DFS로 구해야 한다. 우리는 먼저 간단한 예를 하나 보자.

    4
   / \
  11 13
 / \
7   2

이것은 매우 간단한 예이기 때문에 우리는 가장 긴 경로가 7-11-4-13이라는 것을 쉽게 찾을 수 있다. 그러면 어떻게 귀속으로 정확한 경로와 경로를 찾을 수 있을까?이전의 경험에 따르면 나무의 귀속 해법은 일반적으로 잎 노드로 귀속된 다음에 처리를 시작하면서 뿌리 노드로 거슬러 올라간다.
그러면 우리는 이때 이미 결점 7까지 귀속되었다고 가정하면 좌우자 노드가 없다
1. 따라서 결점 7을 뿌리 결점으로 하는 서브트리의 최대 경로는 7이다.그리고 결점 11로 거슬러 올라가면 결점 11을 뿌리 결점으로 하는 자나무가 가장 큰 경로와 7+11+2=20을 알고 있다.그러나 결점 4로 거슬러 올라갈 때 결점 11에 대해 말하자면 두 개의 경로를 동시에 취할 수 없고 왼쪽 경로나 오른쪽 경로만 취할 수 있기 때문에 뿌리 결점이 4일 때 결점 11은 왼쪽 결점 7만 취할 수 있다. 왜냐하면 7은 2보다 크기 때문이다.따라서 모든 결점에 대해 말하자면 우리는 왼쪽 결점을 지나는path의 합이 큰지 오른쪽 노드를 지나는path의 합이 큰지 알아야 한다.그러면 우리의 귀속 함수 반환값은 현재 결점을 루트 결점으로 하고 잎 노드의 최대 경로의 합으로 정의한 다음에 전체 경로의 최대 값을 매개 변수에 놓고 결과res로 표시할 수 있습니다.
귀속 함수에서 현재 결점이 존재하지 않으면 0을 직접 되돌려줍니다.그렇지 않으면 각각 좌우 서브노드에 대해 귀속 함수를 호출한다. 경로와 마이너스가 될 수 있기 때문에 우리는 당연히 마이너스의 경로와 플러스를 원하지 않는다. 그래서 우리는 0에 비해 비교적 큰 것을 취한다. 바로 플러스를 하지 않거나 플러스를 하려면 플러스를 해야 한다.그리고 전역 최대치 결과res를 업데이트합니다. 바로 왼쪽 결점을 종점으로 하는 최대 path의 합과 오른쪽 결점을 종점으로 하는 최대 path의 합, 그리고 현재 결점 값을 합치면 완전한 경로를 구성합니다.반면에 우리의 반환값은 left와right의 비교적 큰 값을 취하고 현재의 결점 값을 더한다. 왜냐하면 우리의 반환값의 정의는 현재 결점을 종점으로 하는path의 합이기 때문에 left와right에서 비교적 큰 값만 취할 수 있다. 예를 들어 11을 현재 결점으로 한다면 11을 종점으로 하는 가장 큰 경로와,path종합=max(왼쪽, 오른쪽)+11을 구하는 것이다.
참조 코드는 다음과 같습니다.
 

class Solution {
public:
    /**
     * @param root: The root of binary tree.
     * @return: An integer
     */
    int maxPathSum(TreeNode * root) {
        // write your code here
       int ret=INT_MIN;
        onepath(root,ret);
       return ret;
    }
   int onepath(TreeNode*root,int &ret)
    {
        if(root==NULL)
        return 0;
        int left=onepath(root->left,ret);// 
        int right=onepath(root->right,ret);// 
        ret=max(ret,max(0,left)+max(0,right)+root->val);
        return max(left,right)+root->val;
    }

};