LeetCode 풀기 - 654. Maximum Binary Tree

654. Maximum Binary Tree

https://leetcode.com/problems/maximum-binary-tree/

Maximum Binary Tree - LeetCode

문제)

솔루션1) - 재귀

재귀적인 방법으로 왼쪽 서브트리, 오른쪽 서브트리를 구성합니다.

 

풀이 순서

• 초기에 루트 노드를 생성
• nums에서 max 값과 idx를 탐색
• idx 기준으로 왼쪽과 오른쪽으로 나눠서 배열을 나누고 재귀적으로 subtree 구성
• nums가 비어 있으면 재귀 함수는 return None

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def constructMaximumBinaryTree(self, nums):
        # base condition
        if len(nums) == 0: return None        
        
        # 최대 값, 최대 값이 위치한 인덱스 탐색
        (max_val, max_val_idx) = max((v, i) for i, v in enumerate(nums))
        
        # 노드 생성
        node = TreeNode(max_val)
        
        # 왼쪽 서브 트리 구성
        left_nums = nums[0: max_val_idx]
        node.left = self.constructMaximumBinaryTree(left_nums)
        
        # 오른쪽 서브 트리 구성
        right_nums = nums[max_val_idx+1:]
        node.right = self.constructMaximumBinaryTree(right_nums)
                
        return node