[Leetcode]654. Maximum Binary Tree

문제 요약

• 알고리즘 분류:  Tree, 재귀호출
• 난이도: Medium
• 문제내용:
  • • nums배열, 리스트를 주어 줬을때 아래와 같은 트리를 완성 하여라
      • nums에서 가장 큰 값을 루트 노드로 만듭니다.
      • 가장 큰 값의 왼쪽 부분 배열로 왼쪽 서브트리를 재귀적으로 만듭니다.
      • 가장 큰 값의 오른쪽 부분 배열로 오른쪽 서브트리를 재귀적으로 만듭니다.
• 사이트 주소:https://leetcode.com/problems/maximum-binary-tree/description/

문제풀이

 이번 문제는 이진 트리를 완성시켜야 되고 완성시키기 위해서 재귀호출을 사용 해서 풀것이다.

 트리에 대한 자세한 글은 아래 글에서 확인 하여라

https://jih3508.tistory.com/87

[알고리즘 이론] 트리(Tree)

 이번 문제에서는 큰 값 찾는것과 큰 값기준으로 부모노드를 지정하고 그 부모노드 기준으로 배열 왼쪽, 오른쪽 나누면서 자식 노드를 만드는 식으로 하면된다. 그래서 크게 구현 해야하는것은 배열의 최대 값과 최대 값의 인덱스를 찾는 것이 중요하다.  최대 값과 최대 값의 인덱스를 찾은 다음 범위를 지정하고 그 범위 내에서 최대 값과 최대값을 찾는 방식으로 계속 진행 하면된다. 구현은 아래와 같이 그림을 보면 이해가 될것이다.

1. 처음에는 루트 노드를 구하기 위해서는 nums의 최대 값과 최대 값을 인덱스를 찾아야 한다. 찾고 난 다음 그 숫자를 루트 노드로 지정한다.

2. 루트노드가 지정 되었으면 최대 값 기준으로 왼쪽, 오른쪽 나눠서  최대 값을 찾고 자식 노드를 만든다.

3. 2번 과 같은 방법으로 계속 진행해서 leaf 노드가 끝날때 까지 진행 하면된다.

 구현은 이렇게 하면 간단 하게 끝난다. 이번 문제는 Tree에 대한 이해와 간단하게 특정 인덱스 찾는것과 그 범위 지정하는것만 구현만 하면 문제 푸는데는 어렵지 않을것이라고 생각한다. 자세한것은 아래 코드를 보면 될것이다.

Code

Python

class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
        size = len(nums)
        def addNode(start, end):
            if start > end:
                return None
            elif start == end:
                return TreeNode(nums[start])
            else:
                maxValue = max(nums[start: end + 1])
                maxValueIndex = nums.index(maxValue)
                node = TreeNode(maxValue)
                node.left = addNode(start, maxValueIndex - 1)
                node.right = addNode(maxValueIndex + 1, end)
                return node

        maxValue = max(nums)
        maxValueIndex = nums.index(maxValue)
        node = TreeNode(maxValue)
        node.left = addNode(0, maxValueIndex - 1)
        node.right = addNode(maxValueIndex + 1, size - 1)

        return node

Java

class Solution {

    int[] nums;

    public TreeNode constructMaximumBinaryTree(int[] nums) {

        this.nums = nums;

        int maxValue = Arrays.stream(nums).max().getAsInt();
        int mavValueIndex = Arrays.stream(nums).boxed().collect(Collectors.toList()).indexOf(maxValue);
        TreeNode node = new TreeNode(maxValue);
        // Left
        node.left = addTreeNode(0, mavValueIndex - 1);
        //right
        node.right = addTreeNode(mavValueIndex + 1,  nums.length - 1);

        return node;
    }


    // 추가할 노드 탐색
    public TreeNode addTreeNode(int start, int end){
        // start가 end보다 클 경우
        if(start > end){
            return null;
            // 같을 경우는 leaf node 이다.
        }else if (start == end) {
            return new TreeNode(nums[start]);
        }else {
           int maxValue = 0; // 최대값 변수
           int maxValueIndex = -1; // 최대값 index 위치
            for (int i = start; i <= end; i++) {
                if(nums[i] > maxValue){
                    maxValue = nums[i];
                    maxValueIndex = i;
                }
            }

            TreeNode node = new TreeNode(maxValue);
            
            // 최대값 index 기준으로 start부터 최대 index중 왼쪽 노드에 추가한다.
            node.left = addTreeNode(start, maxValueIndex - 1);
            // 최대값 index 기준으로 end까지 오른쪽 노드에 추가한다.
            node.right = addTreeNode(maxValueIndex + 1, end);

            return node;
        }
    }
}