题解 | #二叉搜索树的第k个节点#

什么是二叉搜索树？

定义：二叉查找树，又被称为二叉搜索树。其特点如下：设x为二叉查找树中的一个结点，x节点包含关键字key，一句话就是左孩子比父节点小，右孩子比父节点大，还有一个特性就是”中序遍历“可以让结点有序。 可以看出，在二叉树中：

• 若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
• 任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
• 任意节点的左、右子树也分别为二叉查找树；
• 没有键值相等的节点。

通用方法-层次遍历

先层次遍历 再排序结果 返回[k-1]

class Solution:
    def KthNode(self , proot: TreeNode, k: int) -> int:
        # write code here
        if proot is None or k==0:
            return -1
        queue = []
        queue.append(proot)
        res = [proot.val]
        while len(queue):
            size = len(queue)
            while size:
                root = queue[0]
                queue=queue[1:]
                if root.left is not None:
                    queue.append(root.left)
                    res.append(root.left.val)
                if root.right is not None:
                    queue.append(root.right)
                    res.append(root.right.val)
                size -=1
        if k>len(res):
            return -1
        res.sort()
        return res[k-1]

针对二叉搜索树 中序遍历(非递归)

模板

利用上面的模板改写第11行，做一个判断，如果计数器==k就输出结点值

class Solution:
    def KthNode(self , proot: TreeNode, k: int) -> int:
        # write code here
        if proot is None or k==0:
            return -1
        stack = [] #利用栈实现非递归中序遍历
        p = proot
        c=0 #计数器
        while p is not None or len(stack) >0:
            if p is not None:
                stack.append(p)
                p = p.left
            else:
                p = stack.pop()
                c+=1
                if c==k:
                    return p.val
                p = p.right
        #中序遍历完成了还没输出值就表示k>n 直接返回-1
        return -1

针对二叉搜索树 中序遍历（递归）

如果使用递归方式，其实和层次遍历相比就是不用排序结果