本文共 1452 字，大约阅读时间需要 4 分钟。

题目：给定一棵二叉搜索树，请找出其中的第k小的TreeNode结点。

二叉搜索树的特性：中序遍历后，单调递增。因此关键是写出二叉搜索树的中序遍历。

方法一：通过普通的循环写中序遍历。先把当前结点及其所有左叶结点逐个入栈，在逐个出栈，将其右叶结点入栈。

# -*- coding:utf-8 -*-# class TreeNode:#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneclass Solution:    # 返回对应节点TreeNode    def KthNode(self, pRoot, k):        # write code here        mid = self.mid_tree(pRoot)        if not mid or k < 1 or k > len(mid):            return None        return mid[k-1]    #中序遍历    def mid_tree(self,pRoot):        result = []        tem_stack = []        tem = pRoot        while tem or tem_stack:            while tem:                tem_stack.append(tem)                tem = tem.left            node = tem_stack.pop()            result.append(node)            tem = node.right        return result

方法二：利用递归的思想写遍历。

此方法需要注意的是在类中创建一个空列表（实例变量），通过递归的函数每次向该列表内添加结点。

# -*- coding:utf-8 -*-# class TreeNode:#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneclass Solution:    # 返回对应节点TreeNode    def KthNode(self, pRoot, k):        # write code here        self.myList = []        self.mid_tree(pRoot)        if not self.myList or k < 1 or k > len(self.myList):            return None        return self.myList[k-1]    def mid_tree(self,pRoot):        if not pRoot:            return None        self.mid_tree(pRoot.left)        self.myList.append(pRoot)        self.mid_tree(pRoot.right)

转载地址：https://blog.csdn.net/sinat_42437278/article/details/118182521 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！