Go, Vantage point
가까운 곳을 걷지 않고 서는 먼 곳을 갈 수 없다.
Github | https://github.com/overnew/
Blog | https://everenew.tistory.com/
티스토리 뷰
문제
https://leetcode.com/problems/kth-smallest-element-in-a-bst/description/
Kth Smallest Element in a BST - LeetCode
Can you solve this real interview question? Kth Smallest Element in a BST - 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. Example 1: [https://assets.leetco
leetcode.com
풀이
난이도: Medium
이진트리는 노드의 왼편이 노드의 값보다 작고 오른편은 노드의 값보다 크다.
따라서 노드 값을 작은 순으로 나열하면
왼쪽 서브 트리 -> 루트 노드 -> 오른쪽 서브 트리가 된다.
이러한 순서는 트리를 inorder(중위 순회)로 방문한 것과 동일하다.
따라서 중위 순회 중에 k번째로 방문 완료된 노드가 이진트리이다. K번째로 작은 노드이다.
이 예시로 이 트리는 노드의 값이 작은 순서와 동일하다.
이 트리를 중위 순회하면 실제로 1->2->3->4->5->6 의 순서로 방문하게 된다.
또한 k번째로 방문한 노드까지만 구하면 되므로 모든 노드를 중위 순회하기보다는, K번째에서 중단하는 것이 효율적이다.
물론 단순히 모두 방문하여 값을 기록하고 sort하면 O(N*logN)의 복잡도로 해결가능하지만, inorder로 구하면 방문만 해도 결정이 가능하므로 O(N)의 복잡도로 해결된다.
코드
'알고리즘 공부 > LeetCode' 카테고리의 다른 글
| [LeetCode] 211. Design Add and Search Words Data Structure (C++) (0) | 2023.07.12 |
|---|---|
| [LeetCode] 235. Lowest Common Ancestor of a Binary Search Tree (C++) (0) | 2023.07.07 |
| [LeetCode] 98. Validate Binary Search Tree (C++) (0) | 2023.07.05 |
| [LeetCode] 105. Construct Binary Tree from Preorder and Inorder Traversal (C++) (0) | 2023.07.04 |
| [LeetCode] 572. Subtree of Another Tree (C++) (0) | 2023.07.02 |