iterative solution
# 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
"""
stack,cur,rank=[],root,0
while stack or cur:
if cur:
stack.append(cur)
cur=cur.left
else:
cur=stack.pop()
rank+=1
if rank==k:
return cur.val
cur=cur.right
recursion
# 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
"""
return self.recursion(root,k)
def sizeOfTree(self,root):
if root is None:return 0
size=self.sizeOfTree(root.left)+self.sizeOfTree(root.right)+1
return size
def recursion(self,root,k):
leftSize=self.sizeOfTree(root.left)
if leftSize==k-1:return root.val
elif leftSize<k-1: return self.recursion(root.right,k-leftSize-1)
else:return self.recursion(root.left,k)
