[Leetcode]654. Maximum Binary Tree

1. problem :

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

 

2. solution 1 : 

class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        if (nums.length == 0) {
            return null;
        }
        int maxNumIndex = 0;
        for (int i = 1; i < nums.length; i++) {
            if (nums[maxNumIndex] < nums[i]) {
                maxNumIndex = i;
            }
        }
        TreeNode root = new TreeNode(nums[maxNumIndex]);
        root.left = constructMaximumBinaryTree(Arrays.copyOfRange(nums, 0, maxNumIndex));
        root.right = constructMaximumBinaryTree(Arrays.copyOfRange(nums, maxNumIndex + 1, nums.length));
        return root;
    }
    }

recursion을 이용한 풀이다. 사실 제일 간단한 풀이가 아닐까 싶다. 

 

3. solution 2 :

import java.util.Stack;

public class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        Stack<TreeNode> stack = new Stack<>();
        for (int num : nums) {
            TreeNode current = new TreeNode(num);
            while (!stack.isEmpty() && stack.peek().val < num) {
                current.left = stack.pop();
            }
            if (!stack.isEmpty()) {
                stack.peek().right = current;
            }
            stack.push(current);
        }
    
        return stack.firstElement();
    }
}

이 풀이는 chat gpt 4o가 짜준 풀이다. 시간복잡도가 O(n)이다. 이 풀이는 처음부터 따라가며 이해를 하였다. 

stack의 밑바닥에는 큰 값이 쌓일 것이다라는 생각을 하고 stack을 구성하여야 한다. 

그렇기 위해서, stack이 비어있으면 채워주고, stack이 차있다면, 위의 값과 비교를 해서, 만약에 위의 값보다 크다면, pop을 통해 걷어내고, left로 설정한다. 그러다가 또 비교를 하고, left를 갱신할 수도 있다. 이 과정이 끝나고 나서도, stack에 뭔가가 남아있다면, 그 stack의 수는 current보다 클 것이다. 따라서, right로 설정해 준다. 쉽게 설명하면, "A"라는 육상선수가 제일 1등이라고 생각하고 갔는데, 2등이었다. 그럼 1등이 먼저 도착했다는 소리다. 즉 배열에서 1등 옆에 2등이 있었다는 소리가 된다. 이런 과정을 끝나고, stack에 넣어준다.