[LeetCode] 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

 

Approach

우선 문제에서 Path에 대한 정의가 약간 불친절한데

알아낸 바로는 어떤 leaf 노드에서 다른 leaf 노드까지 부모-자식 관계를 따라 이어진 걸 Path라고 한다

그리고 문제에 있다싶이 leaf 노드에서 leaf 노드까지 갈때 꼭 root를 거칠 필요는 없다.

문제를 풀기 위해서는 Tree를 왼쪽 오른쪽으로 나누고 재귀를 통해 각각의 subtree에서 올라온 path중 높은 값을 골라 return하여 위로 올려주면 되는데,

이렇게만 하면 지금 보고 있는 subtree의 root를 찍고 다시 다른쪽 child로 내려가는 path의 합이 무시된다.

이 값들을 저장하기 위해 이 값을 저장하는 전역변수를 따로 하나 두면 된다.

 

Code

https://github.com/chi3236/algorithm/blob/master/LeetCode_BinaryTreeMaximumPathSum.cpp

불러오는 중입니다...