二叉搜索树的第k个节点

[编程题]二叉搜索树的第k个节点

热度指数：54923 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

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

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

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

数据范围： $0 \le n \le1000$ ， $0 \le k \le1000$ ，树上每个结点的值满足 $0 \le val \le 1000$
进阶：空间复杂度 $O(n)$ ，时间复杂度 $O(n)$

如输入{5,3,7,2,4,6,8},3时，二叉树{5,3,7,2,4,6,8}如下图所示：

该二叉树所有节点按结点值升序排列后可得[2,3,4,5,6,7,8]，所以第3个结点的结点值为4，故返回对应结点值为4的结点即可。

示例1

输入

{5,3,7,2,4,6,8},3

输出

示例2

输入

{},1

输出

-1

备注:

当树是空

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

Python3

liangzhengjie

# 直接递归查找法

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param proot TreeNode类 
# @param k int整型 
# @return int整型
#
class Solution:
    def KthNode(self , proot: TreeNode, k: int) -> int:
        # write code here
        count = [0]
        res = []
        self.traverse(proot, count, k, res)

        if len(res) == 0:
            return -1
        return res[-1]

    def traverse(self, root, count, target, res):
        if root is None:
            return
        if len(res) != 0:
            return

        self.traverse(root.left, count, target, res)
        count[-1] += 1
        if count[-1] == target:
            res.append(root.val)
        self.traverse(root.right, count, target, res)

发表于 2024-05-21 21:11:09 回复(0)

Python3

牛客346399004号

class Solution:
    def KthNode(self , proot: TreeNode, k: int) -> int:
        # write code here
        res = []
        def inorder(root):
            if not root:
                return
            inorder(root.left)
            res.append(root.val)
            inorder(root.right)
        inorder(proot)
        if k > len(res)&nbs***bsp;k <= 0:
            return -1
        return res[k-1]

发表于 2024-04-07 11:53:29 回复(0)

Python3

godylf

先中序遍历所有的节点获得了单调增加的数值序列，然后判断，时间和空间复杂度都是O(n)。

遍历时，NoneType和int以及List<integer>之间的转换和相加出现了卡壳。

自己的较复杂的方案如下，保证递归时返回的结果必然是list类型。

class Solution:
    def midOrder(self,proot:TreeNode):
        if not proot:
            return
        else:
            rootlist=[]
            rootlist.append(proot.val)
            val_list_left=self.midOrder(proot.left)
            val_list_right=self.midOrder(proot.right)
            if val_list_left is None and val_list_right is None:
                return rootlist
            elif val_list_left is None:
                return rootlist+val_list_right
            elif val_list_right is None:
                return val_list_left+rootlist
            else:
                return val_list_left+rootlist+val_list_right
    def KthNode(self , proot: TreeNode, k: int) -> int:
        # write code here
        val_list=self.midOrder(proot)
        if val_list is None&nbs***bsp;k>len(val_list)&nbs***bsp;k<=0:
            return -1
        else:
            return val_list[k-1]

发表于 2022-04-29 17:01:31 回复(0)