[개발자매일영어] Tree - Cracking Coding Interview
이번에는 Tries Interview Question에 대한 내용 입니다.
앞으로는 코딩 인터뷰 문제도 한문제씩 같이 풀어보도록 하겠습니다. 제일 아래에 기출문제가 있습니다. 같이 풀어봐요!
영어 공부는 왕도는 없습니다. 매일 꾸준히 듣고 말하기 연습 하는 것이 가장 중요합니다.
개발자매일영어는 당분간은 Cracking Coding Interview의 저자로 유명한 Gayle Laakmann McDowell저자의 강좌를 지속적으로 공부해보도록 하겠습니다.
전체 분량은 너무 길어서 주요부분 한 두 군데만 1분 이하로 발췌하여 mp3파일로 만들고 있습니다.
즉 한 주제당 1분 이하 분량의 mp3파일이 한 두개씩 제공되겠습니다. 나머지 부분은 리스닝 연습 하시면 되겠습니다.
이번에는 따라하기 쉽도록 최대한 짧게 잘랐습니다.
공부하는 3단계 방법은 아래와 같습니다.
- 1분 분량을 번역
- 전체 듣기 두번
- 문장 듣고 따라 말하기 두번
- 한국말로 듣고 영어로 말하기
하루에 한시간 이상 들으면서 말하기 연습하면 좋을 것 같습니다.
*** 개발자 매일 영어는 제가 개인적으로 공부하기 위해 만든 mp3파일을 혹시 다른 분에게도 도움이 될까 해서 공유하고 있는 것입니다. 부족한 영어 실력으로 번역한 것이라 잘못되었을 수도 있습니다. 이상한 부분은 댓글로 알려 주시면 감사하겠습니다. ***
mp3 파일 다운로드: https://drive.google.com/open?id=1hWAFsFqQp8uDtZGXJhu1B0THsdaJBxys
원본:
----- mp3 script -----
There are some algorithms that can ensure that our tree stays balanced, that is that roughly the same number of nodes will be on the left side the subtree and on the right.
These algorithms get pretty complicated so we're not gonna go into the details here,
but it's worth knowing that they're built into a lot of programming languages and in a lot of cases and interview questions you'll just assume that you have a balanced tree.
The last operation to talk about is traversing or walking through a tree. So there's three common ways we walk through a tree we can do an inorder traversal, a preorder traversal, or a postorder traversal.
A preorder traversal means that you visit the root first and then you visit its
left nodes and it's right nodes. In an inorder traversal you visit the left nodes
first then the current node and then you go to the right nodes. In a postorder
traversal, the root node comes up last so you visit the left nodes and then the right
nodes, then the current root node. Typically in binary search trees we want
to do inorder traversals because that actually allows the nodes to be printed in order. So for example on this tree here with just a 1, a 2, and a 3, the nodes in an in order traversal will actually be printed out in the order one then two then three. So typically we'll see inorder traversals.
-- 번역 예 (직접번역 해보세요) --
왼쪽과 오른쪽 아래 트리를 대략적으로 같게 만드는 트리를 균형되게 하는 몇가지 알고리듬들이 있습니다.
이 알고리듬들은 꽤 복잡해서 여기서 상세히 다루지 않겠지만 많은 개발언어로 구현되고 많은 케이스와 인터뷰 질문들에서 균형된 트리를 사용하는 것으로 가정하므로 알아야할 가치가 있습니다.
마지막으로 탐색에 대해 얘기하겠습니다. 트리 탐색은 순차적 전위적 후위 탐색의 3가지 일반적인 방법이 있습니다.
전위적 탐색은 루트 먼저 방문하고 좌측 노드들과 오른쪽 노드들을 방문하는 것입니다. 순차적 탐색은 좌측 먼저 그리고 현재 노드 그리고 오른쪽 노드들을 방문하는 것입니다. 후위탐색은 루트 노드를 마지막에 오는 것으로 좌측 노드들 그리고 우측 노드들 그리고 현재 루트 노드를 방문하는 것입니다.
일반적으로 노드들을 실제로 순차적으로 인쇄할 수 있어서 이진검색트리들에서 순차적 탐색들을 합니다.
예를들어 1, 2, 3의 노드들을 가지는 순차적 검색 트리는 1, 2, 3으로 출력될 것입니다. 그래서 일반적으로 순차적 탐색들만 다룰 것입니다.
----- 이주의 Interview Question (같이 풀어 봐요!) -----
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:
Input:
2
/
1 3
Output: true
Example 2:
5
/
1 4
/
3 6
Output: false
Explanation: The input is: [5,1,4,null,null,3,6]. The root node's value
is 5 but its right child's value is 4.
문제 링크: https://leetcode.com/problems/validate-binary-search-tree/description/