654-kir3i.md

654. Maximum Binary Tree

Solution

• 시간복잡도: O(N^2)

• 알고리즘

  재귀

• 풀이설명

  문제의 설명대로 재귀적으로 함수를 구성하면 됩니다. base 조건과 예외 케이스만 조심하여 구현하면 됩니다.

• 소스코드

# 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):
        if len(nums) == 1:
            return TreeNode(nums[0])

        m = max(nums)

        if m == nums[0]:
            return TreeNode(m, right=self.constructMaximumBinaryTree(nums[1:]))
        elif m == nums[-1]:
            return TreeNode(m, left=self.constructMaximumBinaryTree(nums[:-1]))
        else:
            mi = nums.index(m)
            return TreeNode(m, left=self.constructMaximumBinaryTree(nums[:mi]),
                            right=self.constructMaximumBinaryTree(nums[mi+1:]))