무제 무제

문제 Say you have an array for which the ith element is the price of a given stock on day i. If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit. Note that you cannot sell a stock before you buy one. Example 1: Input: [7,1,5,3,6,4] Output: 5 Explanation: Buy on day 2 (price = 1) and sell on d..

문제 Given a non-negative integer numRows, generate the first numRows of Pascal's triangle. In Pascal's triangle, each number is the sum of the two numbers directly above it. Example: Input: 5 Output: [ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ] Approach 이전 줄의 원소를 더해 다음 줄을 만들면 된다 굳이 따지자면 DP? Code https://github.com/chi3236/algorithm/blob/master/LeetCode_Pascal'sTriangle.cpp chi3236/algorithm Co..

문제 You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:struct Node { int val; Node *left; Node *right; Node *next; } Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL. Initially, all next pointers are set to NULL...

문제 Given an array where elements are sorted in ascending order, convert it to a height balanced BST. For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1. Example: Given the sorted array: [-10,-3,0,5,9], One possible answer is: [0,-3,9,-10,null,5], which represents the following height balance..

문제 Given preorder and inorder traversal of a tree, construct the binary tree. Note: You may assume that duplicates do not exist in the tree. For example, given preorder = [3,9,20,15,7] inorder = [9,3,15,20,7] Return the following binary tree: 3 / \ 9 20 / \ 15 7 Approach Preorder는 부모 -> 왼쪽 -> 오른쪽 순으로 탐색을 하기 때문에 맨 처음에 나오는 원소가 트리의 루트 노드이다 그리고 Inorder는 왼쪽 -> 부모 -> 오른쪽 순으로 탐색하기 때문에 Preorder의 root를 i..

문제 Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. Note: A leaf is a node with no children. Example: Given binary tree [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 return its depth = 3. Approach DFS를 활용한 inorder traversal로 depth를 측정하거나 BFS를 활용한 level order traversal로 depth를 측정하면 된다. Co..

문제 Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between). For example: Given binary tree [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7 return its zigzag level order traversal as: [ [3], [20,9], [15,7] ] Approach Level Order Traversal인데 기존과 다른 점은 지그재그인것 기존 구현과 비슷한데 차이점은 왼쪽으로 읽을 때는 vec..

문제 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별로 묶어서..