[LeetCode][Python3] 230. Kth Smallest Element in a BST
2019. 1. 15. 08:48 |
프로그래밍/LeetCode
Problem :
https://leetcode.com/problems/kth-smallest-element-in-a-bst/
My Solution :
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def kthSmallest(self, root, k):
"""
:type root: TreeNode
:type k: int
:rtype: int
"""
self.ans = None
self.k = k
def find(node):
if self.ans is None and node:
find(node.left)
self.k -= 1
if self.k == 0:
self.ans = node.val
return
find(node.right)
find(root)
return self.ans
Comment :
전형적인 BST Inorder Traversal 문제이다. 위는 recursion 아래는 stack 활용
My Solution2 :
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def kthSmallest(self, root, k):
"""
:type root: TreeNode
:type k: int
:rtype: int
"""
stack = []
while stack or root:
while root:
stack.append(root)
root = root.left
root = stack.pop()
k -= 1
if k == 0:
return root.val
root = root.right
'프로그래밍 > LeetCode' 카테고리의 다른 글
[LeetCode][Python3] 328. Odd Even Linked List (0) | 2019.01.25 |
---|---|
[LeetCode][Python3] 287. Find the Duplicate Number (0) | 2019.01.25 |
[LeetCode][Python3] 75. Sort Colors (0) | 2019.01.24 |
[LeetCode][Python3] 102. Binary Tree Level Order Traversal (0) | 2019.01.22 |
[LeetCode][Python3] 454. 4Sum II (1) | 2019.01.13 |
[LeetCode][Python3] 78. Subsets (0) | 2019.01.13 |
[LeetCode][Python3] 238. Product of Array Except Self (0) | 2019.01.12 |
[LeetCode][Python3] 347. Top K Frequent Elements (0) | 2019.01.05 |
최근에 달린 댓글 최근에 달린 댓글