654. Maximum Binary Tree

Maximum Binary Tree - LeetCode

중복된 값이 없는 정수로 구성된 list가 주어진다.

이 list를 이용해서 아래 조건에 부합하는 tree를 만들어 root를 반환하는 문제다.

1. Create a root node whose value is the maximum value in nums.
2. Recursively build the left subtree on the subarray prefix to the left of the maximum value.
3. Recursively build the right subtree on the subarray suffix to the right of the maximum value.

조건을 해석해보면 다음과 같다.

1. root는 list에서 가장 큰 값을 val(== maximum value)로 가진다.
2. 왼쪽 서브 트리는 maximum value의 index 왼쪽에 해당하는 값들로 만든다.
3. 오른쪽 서브 트리는 maximum value의 index 오른쪽에 해당하는 값들로 만든다.

1. 재귀 구현

class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
        def dfs(cur_list):
            if not cur_list:
                return None
            pivot = cur_list.index(max(cur_list))

            cur_node = TreeNode(cur_list[pivot], None, None)
            left_list = cur_list[:pivot]
            right_list = cur_list[pivot + 1:]

            cur_node.left = dfs(left_list)
            cur_node.right = dfs(right_list)

            return cur_node

        return dfs(nums)

문제 조건대로 그대로 구현한다.

 

재귀 함수는 cur_list만 들고 진입하고, 내용은 다음과 같다.

1. cur_list에서 가장 큰 값의 index를 찾는다( == pivot)
2. 1번에서 찾은 가장 큰 값을 이용해 cur_node를 만든다. (TreeNode Spec은 주어진다.)
3. pivot을 이용해서 left_list, right_list를 만들어준다.
4. cur_node의 왼쪽 서브 트리는 left_list를 들고 재귀를 타고, 오른쪽 서브 트리는 right_list를 들고 재귀를 탄다.
5. cur_node를 반환한다.
   1. 만일 함수 진입 시에 list의 길이가 0, 즉 cur_list가 없다면(== None) None을 반환한다.