본문 바로가기

알고리즘 문제풀이/leetcode142

[leetcode 105] Construct Binary Tree from Preorder and Inorder Traversal Given preorder and inorder traversal of a tree, construct the binary tree. preorder와 inorder 배열보고 본래 이진 트리 구현하기 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: 풀이: - 난이도는 medium이었지만 몹시 어려웠다. - dfs와 inorder preorder의 개념이 혼합된 문제 - 핵심 개념: inorder는 왼쪽 서브트리 -> 루트 -> 오른쪽 서브 트리 preorder는.. 2020. 10. 24.
[leetcode 78] Subsets Given a set of distinct integers, nums, return all possible subsets (the power set). 가능한 모든 부분집합을 구하라. Note: The solution set must not contain duplicate subsets. Example: Input: nums = [1,2,3] Output: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ] 풀이: 전형적인 백트래킹 문제이다. cnt가 nums길이와 같아지면 종료하지만 그 전에 만들어지는 모든 경우의 수 역시 정답에 저장한다. class Solution { public: vector result; void BackTracking(int cnt, i.. 2020. 10. 24.
[leetcode 104] Maximum Depth of Binary Tree 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], return 3 문제 풀이: -난이도 easy recursion 사용 현재 노드가 nullptr이면 0을 리턴 그렇지 않으면 1씩 더해서 리턴한다. 이 때 왼쪽과 오른쪽 중 큰 값에 1을 더해서 리턴한다. class Solution { public: int m.. 2020. 10. 23.
[leetcode 200] Number of Islands Given an m x n 2d grid map of '1's (land) and '0's (water), return the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water. Example 1: Input: grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ] Output: 1 Exa.. 2020. 10. 23.