[leetCode/JS] 124. Binary Tree Maximum Path Sum

난이도 [ 👿 ] Hard 

 

문제 설명 

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root.

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

Given the root of a binary tree, return the maximum path sum of any non-empty path.

이진 트리의 연속된 경로중에 최대 합산을 반환하면 된다. 루트를 통과할 필요가 없다.

 

 

입출력 예

Example 1:

Input: root = [1,2,3]
Output: 6
Explanation: The optimal path is 2 -> 1 -> 3 with a path sum of 2 + 1 + 3 = 6.

 

Example 2:

Input: root = [-10,9,20,null,null,15,7]
Output: 42
Explanation: The optimal path is 15 -> 20 -> 7 with a path sum of 15 + 20 + 7 = 42.

 

 

Constraints

• The number of nodes in the tree is in the range [1, 3 * 104].
• -1000 <= Node.val <= 1000

 

 

 

---

 

내 솔루션

• DFS로 서치한다. 현재 경로의 합계를 저장해 둔다.
• dfs()의 return은 left, right 노드중 가장 큰 값을 리턴한다.

• return을 0, node.val+left, node.val+right를 하는 이유는 경로의 문제기 때문이다.
• 0을 비교하는 것은 합계가 마이너스가 나오기도해서 하위 노드 경로를 버릴 수 있기 때문이다.

var maxPathSum = function(root) {
  let max = -Infinity;
  const dfs = (node) => {
    if(!node) return 0;
    const left = dfs(node.left);
    const right = dfs(node.right);
    max = Math.max(max, node.val + left + right)
    return Math.max(0, node.val + left, node.val + right);
  }
  dfs(root);
  return max;
};

 

감상평

• 몇일전 풀었던 1026번 문제와 정말 비슷했다.
• 12월은 DFS문제만 쏟아지는 중