C++LeetCode 구현(124.이 진 트 리 의 최대 경로 와)

[LeetCode]124.Binary Tree Maximum Path Sum 이 진 트 리 의 최대 경로 와
Given a non-empty 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.
Example 1:
Input: [1,2,3]
       1
/ \
2   3
Output: 6
Example 2:
Input: [-10,9,20,null,null,15,7]
   -10
/ \
9  20
/  \
15   7
Output: 42
이 두 갈래 나 무 를 구 하 는 가장 큰 경로 와 어 려 운 문제 입 니 다.어 려 우 면 시작 위치 와 끝 위치 에서 임 의 위치 가 될 수 있 습 니 다.블 로 거들 은 당연히 할 줄 모 릅 니 다.그래서 인터넷 에 접속 하여 대 신 들 의 해법 을 보 세 요.이런 나무 와 비슷 한 문 제 는 보통 DFS 로 풀 어야 합 니 다.먼저 간단 한 예 를 들 어 보 겠 습 니 다.
    4
/ \   11 13
/ \ 7   2
이것 은 매우 간단 한 예 이기 때문에 가장 긴 경 로 를 7->11->4->13 으로 쉽게 찾 을 수 있 습 니 다.그러면 어떻게 재 귀 를 통 해 정확 한 경 로 를 찾 을 수 있 습 니까?예전 의 경험 에 따 르 면 나무의 재 귀 해법 은 보통 잎 노드 로 돌아 간 다음 에 처리 하면 서 뿌리 노드 로 거 슬러 올라간다.여기 서 이때 결점 7 로 재 귀 되 었 다 고 가정 하면 좌우 부분 노드 가 없고 결점 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 에서 비교적 큰 값 만 가 져 올 수 있 습 니 다.두 가지 가 아 닙 니 다.코드 는 다음 과 같 습 니 다.

class Solution {
public:
    int maxPathSum(TreeNode* root) {
        int res = INT_MIN;
        helper(root, res);
        return res;
    }
    int helper(TreeNode* node, int& res) {
        if (!node) return 0;
        int left = max(helper(node->left, res), 0);
        int right = max(helper(node->right, res), 0);
        res = max(res, left + right + node->val);
        return max(left, right) + node->val;
    }
};

토론:이 문 제 는 아주 좋 은 Follow up 이 있 습 니 다.바로 이 가장 큰 경 로 를 되 돌려 주 는 것 입 니 다.그러면 복잡 합 니 다.그러면 재 귀 함 수 는 경로 와 결 과 를 되 돌려 주지 못 하고 이 경로 의 모든 노드 로 구 성 된 배열 로 돌아 갑 니 다.재 귀 하 는 매개 변 수 는 최대 경로 의 합 을 유지 하 는 동시에 최대 경로 의 결산 점 의 배열 도 필요 합 니 다.그 다음 에 좌우 부분 노드 에 재 귀 함 수 를 호출 한 후에 얻 은 것 은 배열 입 니 다.배열 의 합 을 통계 하고 0 과 비교 해 야 합 니 다.만약 에 0 보다 작 으 면 0 과 0,배열 이 비 워 야 합 니 다.그 다음 에 가장 큰 경로 와 배열 을 업데이트 하 는 것 입 니 다.값 배열 로 돌아 가 야 합 니 다.코드 가 많이 길 었 습 니 다.관심 있 는 동 화 는 댓 글 에 코드 를 붙 일 수 있 습 니 다~
Github 동기 화 주소:
https://github.com/grandyang/leetcode/issues/124
유사 한 제목:
Path Sum
Sum Root to Leaf Numbers
Path Sum IV
Longest Univalue Path
참고 자료:
https://leetcode.com/problems/binary-tree-maximum-path-sum/
https://leetcode.com/problems/binary-tree-maximum-path-sum/discuss/39775/Accepted-short-solution-in-Java
https://leetcode.com/problems/binary-tree-maximum-path-sum/discuss/39869/Simple-O(n)-algorithm-with-one-traversal-through-the-tree
C++구현 LeetCode(124.이 진 트 리 의 가장 큰 경로 와)에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++구현 이 진 트 리 의 가장 큰 경로 와 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 조회 하 시기 바 랍 니 다.앞으로 도 많은 지원 바 랍 니 다!