Binary Tree Maximum Path Sum - LeetCode

Problem

1. input: 이진 트리의 루트 노드 root
2. output: 주어진 트리의 경로(중복된 노드 X)중 노드 값의 합의 최댓값 리턴

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

Idea

일단 먼저 트리에서 경로의 특징을 살펴보면,

1. 한 노드의 좌,우 자식이 모두 경로에 포함되는 경우는 해당 노드와 자식들을 잇는 경우 밖에 없다.

   

2. 1이 아닌 경우는 노드의 좌,우 자식 중, 합이 최대가 되는 하나의 자식만 경로에 포함된다.

   

즉, 리프노드부터 거슬러 올라오며 위의 1, 2중 합이 최대가 되는 경우를 경로에 포함시키면 된다. (DFS탐색 후, 리턴 값을 통해 값을 반환하면 리프 → 로트 역순으로 처리 가능)→ Sol1

Solution

1. DFS

   DFS탐색을 통해 리프노드까지 내려간 후, 리턴 값을 통해 합이 최대인 노드만 선택하며 루트노드로 올라오는 방식

   DFS 탐색 후, 리턴 경우의 수

   • 좌, 우 노드중 하나만 포함 + 자기자신
   • 좌, 우 노드 둘다 포함 X (둘다 음수) + 자기자신

   리턴 전에 서브 트리의 경로가 합의 최댓값일 수 있으므로 중간에 한번 확인해줌 → idea의 1번 경우

   /**
    * Example:
    * var ti = TreeNode(5)
    * var v = ti.`val`
    * Definition for a binary tree node.
    * class TreeNode(var `val`: Int) {
    *     var left: TreeNode? = null
    *     var right: TreeNode? = null
    * }
    */
   class Solution {
       var answer = Int.MIN_VALUE
       fun maxPathSum(root: TreeNode?): Int {
           recSearch(root)
           return answer
       }
   
       fun recSearch(root: TreeNode?): Int {
           if (root == null) return 0
           val left = maxOf(recSearch(root!!.left), 0) // 왼쪽 자식 or 0 (음수일 경우)
           val right = maxOf(recSearch(root!!.right), 0) // 오른쪽 자식 or 0 (음수일 경우)
           answer = maxOf(answer, left + right + root!!.`val`) // idea의 1번 경우
           return maxOf(left, right) + root!!.`val` // 좌,우 자식중 큰 값 + 자기자신 리턴
       }
   }
   

   시간 복잡도: 트리 탐색 = n

   

Point

1. 예에에전에 리턴 값으로 트리 역방향 처리를 할 줄 몰라서, 리프노드를 따로 저장하고 다시 탐색했던 슬픈 기억이…