LeetCode 28 Binary Tree Maximum Path Sum

1619 단어 차례로 돌아가다나무가 두루 다니다
Given a binary tree, find the maximum path sum.
The path may start and end at any node in the tree.
For example:
Given the below binary tree, 
  1
 / \
2   3

Return 6.
분석:
방금 문제를 보고 그림 알고리즘인 줄 알고 가장 큰 경로를 찾았다.그러나 나무가 방향도가 있는 것을 감안하면 하위 노드에서 아버지 노드까지 직접 훑어볼 수는 없다.
그러나 임의의 노드에 대해서는 이 노드가 시작되는 (즉 이 노드는 경로의 한쪽) 아래로 흐르는 최대 경로와 를 계산할 수 있다.
위의 인식이 생기면,
어떤 노드에 대해 우리는 왼쪽 아이의 경로, 오른쪽 아이의 경로와 현재 노드를 임의의 두 점 사이의 경로로 조합할 수 있다. (이 경로는 현재 노드를 통과한다.)
기왕 임의의 두 점의 경로가 이렇게 구성될 수 있다면 임의의 두 점 간의 경로와 구할 수 있다.
생각이 뚜렷해지면
우리는 나무를 두루 돌아다니며 각 노드를 통과하는 가장 큰 경로를 구하고 비교하면 된다.
몇 가지 참고 사항:
1, 귀속 접근 시 함수는 현재 노드로 시작하는 최대 경로와
2, 자바에서 매개 변수는 값 전달이기 때문에 max는 인용 변수라면 가장 간단한 것은 수조이다. 원소가 하나밖에 없는 수조로 성명하면 된다.
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int maxPathSum(TreeNode root) {
        //max 
        int[] max = new int[1];
        max[0] = Integer.MIN_VALUE;
        calSum(root, max);
        return max[0];
    }
    // node 
    public int calSum(TreeNode node, int[] max){
        if(node == null)
            return 0;
        
        int left = calSum(node.left, max);
        int right = calSum(node.right, max);
        // 
        int current = Math.max(node.val, Math.max(node.val+left, node.val+right));
        // max
        max[0] = Math.max(max[0], Math.max(current, left+node.val+right));
        
        return current;
    }
}
[Unity 2D] 0부터 시작하는 Log like 제작 기록의 1~라운드 이동 스크립트에 대한 생각~
문제를 풀다--두 갈래 나무(2)

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage