두 갈래 나무: 최대 경로와 (방법 및 설명)

Leetcode 질문124. Binary Tree Maximum Path Sum을 참조하십시오.

In my personal opinion, this question has the ability to judge your analytical and tree traversal skills. You must give it a try before jumping onto solution.
By that you might get to know how ruthless this problem is. At the end of this article you would develop the thinking capability and would be able to solve problems like path-sum, longest-branch, diameter of a tree etc. See related problems at the end. Cheers!

문제 진술

주어진 root의Binary Tree, 그 어떠한 maximum path sum의non-empty path도 되돌려준다.
두 갈래 나무의 Apath는 하나의 노드 서열로 서열의 각 인접 노드는 그들의 가장자리를 연결한다.노드는 순서대로만 나타날 수 있다at most once.경로는 루트를 통과할 필요가 없습니다.

The path sum of a path is the sum of the node's values in the path.

예1:

입력:root = [1,2,3]출력: 6설명: 최적 경로는 2->1->3, 경로와 2+1+3=6입니다.

예2:

입력:root = [-10,9,20,null,null,15,7]출력: 42설명: 최적 경로는 15->20->7, 경로와 15+20+7=42입니다.

직각

우리는 우선 문제 진술을 자세하게 이해하고 몇 가지 관건을 지적해야 한다.

Path: 첫 번째 시도에서 일반적인 뿌리에서 잎까지의 경로처럼 들리지만 주어진 뿌리에 대해서는 모두 branch이다.Apath는 일반적으로 1개 이상의 인접(연결 및 연속) 노드로 구성된 체인입니다.그것, 경로, 포함할 수도 있고 포함하지 않을 수도 있다root 자체.이것이 바로 문제의 본질이다. 그것이 요구하는 것은 우리에게 최대와 최대의 경로를 제공하는 것이다.

Non-Empty Path: 이것은 일리가 있는 것이다. 왜냐하면 우리는 제로 경로를 계산할 수 없기 때문이다.

At most once: 유효한 경로가 노드를 여러 번 포함할 수 없다는 것을 고려해야 한다.

우리가 잘 알고 있는 바에 의하면 가장 큰 경로가 근본체가 존재하지 않을 수도 있다. 이것은 우리가 추측하는 모든 알고리즘에 대해 우리는 모든 노드에 귀속적으로 접근해야 한다는 것을 의미한다.아마도 우리의 가장 큰 경로는 어딘가에 있을 것이다.아래의 예시를 참고하여 더욱 분명하게 하세요.

5개 노드 또는 4개 모서리에 여러 경로가 있을 수 있지만우리는 그것들을 열거할 것이다.
노드 2부터 시작:

2:sum=2

2<-->-3:sum=-1

2<-->-3<-->3:sum=2

2<-->-3<-->3<-->4:sum=6

2<-->-3<-->3<-->5:sum=7

노드 3부터 시작:

-3:sum=-3

-3<-->3:sum=0

-3<-->3<-->4:sum=4

-3<-->3<-->5:sum=5

노드 3부터 시작:

3:sum=3

3<-->4:sum=7

3<-->5:sum=8

노드 4부터 시작:

4:sum=4

4<-->3<-->5:sum=12

노드 5부터 시작:

5:sum=5

합계를 계산할 때 경로 순서가 중요하지 않으므로 경로3 -> 4는 4 ->3와 같을 것입니다.
되돌아오는 경로2 <--> -3 <--> 3의 최대 크기와 (sum은 2)가 의미가 있습니까?
아니요!경로4 <--> 3 <--> 5의 출력은 12이므로 녹색으로 강조 표시된 노드를 참조하십시오.
이제 우리의 논리를 세워 봅시다.우리는 모든 뚜렷한 배열을 고려할 것이다.

1. 좌/우 서브 트리 없음(단일 노드 또는 잎 노드)

만약 당신이 나무를 두루 돌아다니며 손을 더럽혔다면,curr가 가장 왼쪽을 가리키는 노드나 잎사귀의 노드를 가리키는 상황을 만날 수 있습니다.
우리는 과거에 종종 이 노드를 창고 위에 놓았다. 그리고, 우리의curr는 순서에 따라 왼쪽이나 오른쪽을 가리켰다.

Remember, single node is also a valid path!

현재, 경로와, 우리는 왼쪽이나 오른쪽의 값이 없기 때문에, 우리는 노드 값으로 직접 되돌아갈 것이다.
좌우 두 아이가 모두 존재한다면?이런 상황에서 우리는 이것이 도모할 수 있는 이익이 있는지 평가할 것이다.

2. 서브트리가 존재할 때(수익/이윤 평가)

논리를 토론하기 전에, 당신은 우리에게 -1와 -2를 고려해서 최대치를 얻어야 하는지 알려줄 수 있습니까?아니요!우리는 노드1만 잘하기 때문에 왜 이렇게 해야 합니까?
경로에 -1 또는 -2를 추가하면 우리의 최대치를 더욱 낮출 수 있습니다. 이것은 손익과 유사합니다.그렇다면, 우리는 어떻게 이런 논리를 프로그래밍해야 합니까?
이거 어때요?

지금 노드3를 추가할까요?지난 그림에서 우리의 가장 큰 합은 1이다.이 예에서 만약 우리가 새로운 노드3를 사용한다면 우리의 최대화는 2가 된다.
그래서 우리의 새로운 경로는 1 -> -2 -> 3, 최대와 2로 바뀌었다.
더 놀라운 것은 우리가 틀렸다는 것이다.이것은 우리가 주의해야 할 일이다.
노드1에서 3까지의 경로는 선택하지 않습니다.자세히 살펴보면 노드3의 최대치만 더 크다.
path1 -> -2 -> 3만 있는 것보다 path3의 이윤이 더 낮다.
우리는 여기서 몇 가지 관건을 추단해 낼 수 있다.

우리는 왼쪽과 오른쪽의 최대 합을 얻어야 한다.함수 someMethodToGetMaximumSumFromTreeNode 를 만듭니다. 함수 TreeNode 를 받아들일 것입니다.int leftMax = someMethodToGetMaximumSumFromTreeNode(curr.left) int rightMax = someMethodToGetMaximumSumFromTreeNode(curr.right)

만약에 다른 지점에서 참관해야 한다면 우리는 좌우로 갈 수 없다. 다시 말하면 우리는 세 갈래의 길이 있을 수 없다.
따라서 우리는 왼쪽 최대치나 오른쪽 최대치 중에서 최대치를 선택하고 이 경로를 부모 경로와 결합시켜 경로를 얻어야 한다.우리는 그것을 maxChildren

라고 부른다int maxChildren = Math.max(leftMax, rightMax)

우리는 전류에 왼쪽이나 오른쪽을 추가하는 것이 증가하거나 경로가 총화되거나 감소하는지 확인해야 한다.어떻게?우리는 Math.max() 함수를 왼쪽과 오른쪽에 사용해야 한다.int maxWithRoot = Math.max(curr.val, (curr.val + maxChildren))

우리는 왼쪽, 오른쪽 및 뿌리가 더 큰 값을 형성했는지 검사해야 합니까?이것은 모든 노드를 추가한 나무[1,2,3]입니다.
우리는 그것을 maxNode라고 부른다.int maxNode = Math.max(maxWithRoot, root.val + leftMax + rightMax)

가장 큰 합을 계산하는 마지막 부분은 더 큰 경로와 새로운 합을 찾았는지 여부이다.우리는 그에 상응하여 우리의 답안을 갱신해야 한다.maxSum = Math.max(maxSum, maxNode)

그래서 이것은 모두 이윤 창출 능력을 평가하고 Biger max가 우리의 질문에 대답하도록 돕는 것에 관한 것이다.
그러나 우리는 아직 귀환 유형과 함수 논리someMethodToGetMaximumSumFromTreeNode를 연구하지 못했다.
모든 트리 노드에 대해 이 함수는 루트가 지정될 때까지 최대 경로와 루트를 계산합니다.
그래서 한 그루의 나무[1, 2, 3]에 대해leftMax는2,rightmax는3,반환값은2과3+근값의 최대값이다.
우리는 이미 이런 논리가 있습니까?맞아요!maxWithRoot를 참조하십시오. 이것은 우리가 함수에서 되돌아오는 내용입니다.

Note that, we are evaluating our answer in variable maxSum whereas the return value for the function is returned by maxWithRoot

복잡성 분석

Time complexity: O(N), 그 중에서 N는 노드 수입니다. 저희가 각 노드를 두 번 이상 방문하지 않기 때문입니다.Space complexity: O(H), 그 중에서 H는 나무의 높이로 귀속 창고를 유지하는 데 쓰인다.평균적으로 트리 높이는 H=logN, 기울어진 트리의 최악의 경우 H=N입니다.

절차.

class Solution {
  int maxSum = Integer.MIN_VALUE;

  public int maxPathSum(TreeNode root) {
    //recurse(root);
    getMaxPathSum(root);
    return maxSum;
  }

    int recurse(TreeNode root){

        if(root == null) return 0;

        int leftMax = recurse(root.left);
        int rightMax = recurse(root.right);

        int maxChildren =  Math.max(leftMax, rightMax);

        int maxWithRoot = Math.max(root.val, (root.val + maxChildren));

        int maxNode = Math.max(maxWithRoot, root.val + leftMax + rightMax);

        maxSum = Math.max(maxSum, maxNode);

        return maxWithRoot;

    }

    // Enhanced version of our logic
    private int getMaxPathSum(TreeNode root) {

        if (root == null) return 0;

        int leftMax = Math.max(0, getMaxPathSum(root.left)); // Take 0 instead of a negative left sum
        int rightMax = Math.max(0, getMaxPathSum(root.right)); // Take 0 instead of a negative right sum

        maxSum = Math.max(maxSum, (leftMax + rightMax + root.val));

        return Math.max(leftMax, rightMax) + root.val;
    }

}

테스트 용례

이 점에 대해 나는 몇 가지 가장자리 사례를 열거하였는데, 너는 해결 방안을 제출하기 전에 시도해야 한다

[1]
[-1]
[1,null, 1]
[2, -1]
[2, -1, -2]
[1,2,3]
[1,2,3,1,3,2,null,1]
[3,9,20,null,null,15,7]
[1,-2,-3,1,3,-2,null,-1]
[-10,9,20,null,null,15,7]
[1,2,3,null, null,4,5,6,7,8,9,10]
[5,4,8,11,null,13,4,7,2,null,null,null,1]
[1,2,3,null, null, 4,5,6,7, null,8,9, null, 10, 11, null, null,12, 13, 14, null, 15, null,16, null, null, 17, null, null, 18, null]
[-1,null, -1,null, -1,null, -1,null, -1,null, -1,null, -1,null, -1,null, -1,null, -1,null, -1,null, -1,null, -1,null, -1,null, -1,null, -1,null, 16]

관련 문제

Path Sum

Sum Root to Leaf Numbers

Path Sum IV

Longest Univalue Path

Time Needed to Inform All Employees

Diameter of Binary Tree

PS: 이 문제에 대한 설명 및 방법을 계속해서 살펴보십시오.