JZ54 二叉搜索树的第k个节点

JZ54 二叉搜索树的第k个节点

描述：

给定一棵结点数为n 二叉搜索树，请找出其中的第 k 小的TreeNode结点值。

1. 返回第k小的节点值即可

2. 不能查找的情况，如二叉树为空，则返回-1，或者k大于n等等，也返回-1

3. 保证n个节点的值不一样

思路：二叉搜索树排序的过程就是中序遍历的过程，因此代码结构与二叉树中序遍历类似，将中序遍历的结果存在数组中，返回数组第k-1个元素即可。

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def __init__(self):
        self.nodes = []
    def KthNode(self , proot: TreeNode, k: int) -> int:
        if proot == None or k==0:
            return -1
        self.inOrder(proot)
        if len(self.nodes)>=k: return self.nodes[k-1]
        else: return -1
    def inOrder(self, proot: TreeNode):
        if not proot:
            return 
        self.midOrder(proot.left)
        self.nodes.append(proot.val)
        self.midOrder(proot.right)

最后

以上就是火星上蜗牛为你收集整理的JZ54 二叉搜索树的第k个节点的全部内容，希望文章能够帮你解决JZ54 二叉搜索树的第k个节点所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。