题目描述:给定一棵二叉搜索树,请找出其中的第 k 小的结点。例如, (5,3,7,2,4,6,8) 中,按结点数值大小顺序第三小结点的值为 4。
Solutions
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# 返回对应节点TreeNode
def KthNode(self, pRoot, k):
# write code here
if pRoot is None or k <= 0:
return None
stack = []
node = pRoot
res = []
while node is not None or len(stack) > 0:
if node is not None:
stack.append(node)
node = node.left
else:
node = stack.pop()
res.append(node)
node = node.right
if len(res) < k:
return None
return res[k-1]
# 运行时间:28ms
# 占用内存:5720k
为了不要总在编程上纠结太久,可以用下面的方式,将中序遍历看成内部函数:
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# 返回对应节点TreeNode
def KthNode(self, pRoot, k):
# write code here
if pRoot is None or k <= 0:
return None
res = []
def inorder(root):
if root is None:
return
inorder(root.left)
res.append(root)
inorder(root.right)
inorder(pRoot)
if len(res) < k:
return None
return res[k-1]
# 运行时间:35ms
# 占用内存:5624k