무제 무제

문제 Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level). For example: Given binary tree [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 return its level order traversal as: [ [3], [9,20], [15,7] ] Approach 그냥 level order 출력만 하면 BFS만 하면 되는데 Level별로 따로 묶어서 출력해야 하는게 까다로운 부분이다 한 층을 다 넣은 큐의 초기 크기를 초기값으로 하는 for문을 돌려 1씩 빼면서 개수를 세고 Level별로 묶어서..

문제 Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center). For example, this binary tree [1,2,2,3,4,4,3] is symmetric: 1 / \ 2 2 / \ / \ 3 4 4 3 But the following [1,2,2,null,3,null,3] is not: 1 / \ 2 2 \ \ 3 3 Approach 처음에는 트리를 왼쪽, 오른쪽 서브트리로 나누고 왼쪽으로 치는 가지, 오른쪽으로 치는 가지를 각각 +1 -1, 값도 +, - 해서 둘을 더해 0이 되면 대칭이다 이렇게 생각해 풀었는데 교묘하게 이를 만족하면서 대칭이 아닌 트리가 있어서 실패했다. 그..

문제 Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is defined as follows: The left subtree of a node contains only nodes with keys less than the node's key. The right subtree of a node contains only nodes with keys greater than the node's key. Both the left and right subtrees must also be binary search trees. Example 1: 2 / \ 1 3 Input: [2,1,3] Output: true..

문제 Given a binary tree, return the inorder traversal of its nodes' values. Example: Input: [1,null,2,3] 1 \ 2 / 3 Output: [1,3,2] Follow up: Recursive solution is trivial, could you do it iteratively? Apporach Inorder traversal: 왼쪽 자식-> 자신 -> 오른쪽 자식 순으로 트리 탐색 Recursive로 풀면 직관적이고 함수 스택 말고 실제 stack을 활용해 반복문으로 풀 수도 있다. Code Recursive: https://github.com/chi3236/algorithm/blob/master/LeetCode_Binary..

문제 A message containing letters from A-Z is being encoded to numbers using the following mapping:'A' -> 1 'B' -> 2 ... 'Z' -> 26 Given a non-empty string containing only digits, determine the total number of ways to decode it. Example 1: Input: "12" Output: 2 Explanation: It could be decoded as "AB" (1 2) or "L" (12). Example 2: Input: "226" Output: 3 Explanation: It could be decoded as "BZ" (2 ..

문제 Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array. Note: The number of elements initialized in nums1 and nums2 are m and n respectively. You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. Example: Input: nums1 = [1,2,3,0,0,0], m = 3 nums2 = [2,5,6], n = 3 Output: [1,2,2,3,5,6] Ap..

문제 Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogram. Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3]. The largest rectangle is shown in the shaded area, which has area = 10 unit. Example: Input: [2,1,5,6,2,3] Output: 10 Approach i번째 막대에서 가장 큰 직사각형을 만드려면 i번째 막..

문제 Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once. Example: board = [ ['A','B','C','E'], ['S','F','C','S'], ['A','D','E','E'] ] Given word = "ABCCED", return true. Given word = "SEE"..