바위타는 두루미

230. Kth Smallest Element in a BST Given a binary search tree, write a function kthSmallest to find the kth smallest element in it. Note: You may assume k is always valid, 1 ≤ k ≤ BST's total elements. Example 1: Input: root = [3,1,4,null,2] k = 1 3 / \ 1 4 \ 2 Output: 1 Example 2: Input: root = [5,3,6,2,4,null,null,1], k = 3 5 / \ 3 6 / \ 2 4 / 1 Output: 3 Follow up: What if the BST is modified..

116. Populating Next Right Pointers in Each Node 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...

105. Construct Binary Tree from Preorder and Inorder Traversal 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 # Definition for a binary tree node. # class TreeNode(object): # def __init..

103. Binary Tree Zigzag Level Order Traversal Given a binary tree, return the zigzag level ordertraversal 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] ] class Solution(object): def zigzagLevel..

94. Binary Tree Inorder Traversal 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] class Solution(object): def inorderTraversal(self, root): """ :type root: TreeNode :rtype: List[int] """ if not root: return [] else: return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right)

160. Intersection of Two Linked Lists Write a program to find the node at which the intersection of two singly linked lists begins. For example, the following two linked lists: begin to intersect at node c1. Example 1: Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3 Output: Reference of the node with value = 8 Input Explanation: The intersected node's va..

2. Add Two Numbers You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list. You may assume the two numbers do not contain any leading zero, except the number 0 itself. Example: Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8 E..

문제 정수 배열에서 peak란 현재 원소가 인접한 정수보다 크거나 같을 때를 말하고, 'valley'란 현재 원소가 인접한 정수보다 작거나 같을 때를 말한다. 예를 들어 {5,8,6,2,3,4,6}이 있으면, {8,6}은 peak고 {5,2}는 valley인 것이다. 정수배열이 주어졌을때 'peak'와 'valley'가 번갈아 등장하도록 정렬하는 알고리즘을 작성하라. 해법 1. 부분 최적 해법 배열을 정렬하고 위치를 바꿈으로써 peak와 valley를 순차적으로 나올 수 있도록 만들 수 있을 것이다. 정렬된 배열 0 1 4 7 8 9 가 있다고 하자. 0은 올바른 위치고 1은 잘못 놓였다 0과 4중에 자리를 바꿀 수 있으나 0와 바꿔보자 7도 잘못 놓였다. 4과 8중에 자리를 바꿀 수 있으나 4과 바꿔보..

문제 정수 스트림을 읽는다고 하자. 주기적으로 어떤 수 x의 랭킹(x보다 같거나 작은 수의 갯수)를 확인하고 싶다. 해당 연산을 지원하는 자료구조와 알고리즘을 구현하라. 수 하나를 읽을 때마다 호출되는 메서드 track(int x)와, x보다 작거나 같은 수의 갯수( x자신을 제외)를 반환하는 메서드 getRankOfNumber(int x)를 구현하라 입력 : 5,1,4,4,5,9,7,13,3 출력 : getRankOfNumber(1) = 0 getRankOfNumber(3 ) = 1 getRankOfNumber(4 ) = 3 해법 모든 원소를 정렬된 상태로 보관하는 배열을 사용하면 구현하기가 상대적으로 간단해진다. 새로운 원소를 삽입할때마다 다른 원소들을 옆으로 옮겨 공간을 확보해야하는데 그렇다보면 t..

문제 각 행과 열이 오름차순으로 정렬된 MXN 행렬이 주어졌을대, 특정한 원소를 찾는 메서드를 구현하라 해결법 첫번째 : 행마다 이진탐색을 할 수있다. M개의 행이 있고 각 행을 탐색하는데 O(logN)이 걸리기 떄문에 O(MlogN)이 될 것이다. 두번재 해결법을 생각해보기 전에 규칙을 찾아보자 15 20 40 85 20 35 80 95 30 55 95 105 40 80 100 200 이런 행렬이 주어졌을때 55를 찾아보자. 행의 시작점이나 열의 시작점을 보면 위치를 유추해 볼 수 있다. 열의 시작점 원소의 값이 55보다 크다면 탐색할 필요가 없고, 마찬가지로 행의 시작점 원소의 값이 55보다 크다면 탐색할 필요가 없을 것이다. 그러면 행이나 열의 마지막점에서도 똑같이 적용할 수 있다. 어떤 행이나 열..