Done is better than perfect

본 포스팅 시리즈에서는 모든 프로그래머들이 반드시 알아야 할 가장 기본적인 자료구조를 다룰 예정이다. 앞으로 다룰 내용은 프로그래머에게 기본 소양이며, 본인 스스로 직접 구현할 수 있어야 한다. | 다섯 번째 순서는 트리이다. 트리는 계층적으로 구성되어 있고 서로 연결되어있는 데이터에 적합한 계층적 자료구조이다. 이 구조는 링크드 리스트 와는 다른 자료구조이지만, 링크된 요소끼리는 선형 순서로 링크드 리스트라고도 볼 수 있다. 트리는 오래전부터 다양한 형태로 계속 연구되어 발전되어 왔고, 활용되었으며 또 특정 상황 및 애플리케이션에 맞는 제약사항을 가지게 되었다. 트리의 형태로는 대부분이 알고 있는 이진 탐색 트리부터 B 트리, 레드 블랙 트리, AVL 트리 등이 있다. 이진 탐색 트리는 말 그대로 데이..

Question Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree. 이진 탐색 트리와 정수 k가 주어졌을 때, 모든 노드 중 k번째로 작은 값을 리턴하는 함수를 작성하라. 제약사항 The number of nodes in the tree is n. 1 right); } int kthSmallest(TreeNode* root, int k) { vector node_val_vec; AddAllElement(node_val_vec, root); return node_val_vec[k-1]; } }; Time..

Question 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 s..

Question Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree. 이진 탐색 트리의 preorder 순서와 inorder순서로 탐색한 결과인 두 배열이 주어질 때, 원래의 이진트리를 출력하라. 제약사항 1

Question Given the root of a binary tree, return the zigzag level order traversal of its nodes' values. (i.e., from left to right, then right to left for the next level and alternate between). 이진트리의 root 가 주어졌을 때 지그재그로 노드의 값을 출력하는 함수를 작성하라. 제약사항 The number of nodes in the tree is in the range [0, 2000]. -100 left){ next_level.push(top->left); } if(top->right){ next_level.push(top->right); } }els..