Skip to content

Instantly share code, notes, and snippets.

@jovianlin
Created December 15, 2018 02:32
Show Gist options
  • Save jovianlin/92c07a954c84e96405c9e378305cf77f to your computer and use it in GitHub Desktop.
Save jovianlin/92c07a954c84e96405c9e378305cf77f to your computer and use it in GitHub Desktop.
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def kthSmallest(self, root, k):
"""
:type root: TreeNode
:type k: int
:rtype: int
"""
from collections import deque
stack = deque()
while root.left:
stack.append(root)
root = root.left
return self.foo(root, k, stack)
def foo(self, root, k, stack):
print
if k == 1:
return root.val
if root.right is not None:
root = root.right
stack.append(root)
while root.left is not None:
root = root.left
stack.append(root)
root = stack.pop()
return self.foo(root, k-1, stack)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment