[해커랭크(Hackerrank)/30 Days of Code/파이썬3(python3)] Day 22: Binary Search Trees

Objective
Today, we're working with Binary Search Trees (BSTs). Check out the Tutorial tab for learning materials and an instructional video!

Task
The height of a binary search tree is the number of edges between the tree's root and its furthest leaf. You are given a pointer, , pointing to the root of a binary search tree. Complete the getHeight function provided in your editor so that it returns the height of the binary search tree.

Input Format

The locked stub code in your editor reads the following inputs and assembles them into a binary search tree:
The first line contains an integer, , denoting the number of nodes in the tree.
Each of the subsequent lines contains an integer, , denoting the value of an element that must be added to the BST.

Output Format

The locked stub code in your editor will print the integer returned by your getHeight function denoting the height of the BST.

Sample Input

7
3
5
2
1
4
6
7

Sample Output

3

Explanation

The input forms the following BST:

The longest root-to-leaf path is shown below:

There are nodes in this path that are connected by edges, meaning our BST's . Thus, we print as our answer.

풀이

class Node:
    def __init__(self,data):
        self.right=self.left=None
        self.data = data
class Solution:
    def insert(self,root,data):
        if root==None:
            return Node(data)
        else:
            if data<=root.data:
                cur=self.insert(root.left,data)
                root.left=cur
            else:
                cur=self.insert(root.right,data)
                root.right=cur
        return root

    def getHeight(self,root):
        result = -1
        if root:
            left_depth = self.getHeight(root.left)
            right_depth = self.getHeight(root.right)
            result = left_depth + 1 if left_depth > right_depth else right_depth + 1
        return result
        
        
T=int(input())
myTree=Solution()
root=None
for i in range(T):
    data=int(input())
    root=myTree.insert(root,data)
height=myTree.getHeight(root)
print(height)       

설명

이진탐색트리의 높이를 구하는 문제이다. 이진트리는 다음과 같은 특성을 갖고 있다.

• 각 노드의 왼쪽 서브트리에는 해당 노드의 값보다 작은 값을 지닌 노드들로 이루어져 있다.
• 각 노드의 오른쪽 서브트리에는 해당 노드의 값보다 큰 값을 지닌 노드들로 이루어져 있다.
• 중복된 노드가 없어야 한다.
• 왼쪽 서브트리, 오른쪽 서브트리 또한 이진탐색트리이다.

출처는 이곳이며 이진탐색트리가 무엇인지 엄청 자세하게 설명돼있다. 각종 자료구조와 알고리즘이 자세하게 설명돼있는데 정말 좋은 블로그이다. 아무튼 그 높이를 구하는 방법은 위 풀이에서 getHeight라는 함수를 참조하면 된다. 재귀형식으로 각 왼쪽과 오른쪽으로 깊이를 탐색하고 끝에 도달했을 때 +1을 더해서 반환한다. 문제 출제의 그림을 보면 Longest Root-to-Leaf Path가 3, 5, 6, 7로써 총 4단계에 해당하는 것을 알 수 있는데 왜 반환되는 3이 정답이냐 하면 root는 트리의 높이에 포함되지 않기 때문이다.