62 二叉搜索树的第k个结点

题目描述

给定一棵二叉搜索树，请找出其中第k大的节点。

解题思路

核心思想：中序遍历二叉搜索树得到有序序列，第k个节点就是第k大的节点。

Python 实现

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def kth_node(root, k):
    """
    找出二叉搜索树第k大的节点

    Args:
        root: 二叉搜索树根节点
        k: 第k大

    Returns:
        TreeNode: 第k大的节点
    """
    if not root or k <= 0:
        return None

    result = []
    index = 0

    def inorder(node):
        nonlocal index
        if not node or index >= k:
            return

        inorder(node.left)
        if index < k:
            result.append(node)
            index += 1
        inorder(node.right)

    inorder(root)

    return result[k - 1] if k <= index else None


# 测试代码
if __name__ == "__main__":
    # 构建BST:
    #     5
    #    / \
    #   3   7
    #  / \ / \
    # 2  4 6  8
    root = TreeNode(5)
    root.left.left = TreeNode(3)
    root.right.left = TreeNode(7)
    root.left.left.left = TreeNode(2)
    root.left.left.right = TreeNode(4)
    root.right.left.left = TreeNode(6)
    root.right.left.right = TreeNode(8)

    for k in range(1, 9):
        node = kth_node(root, k)
        if node:
            print(f"第{k}大: {node.val}")
        else:
            print(f"第{k}大: 不存在")

# 输出:
# 第1大: 2
# 第2大: 3
# 第3大: 4
# 第4大: 5
# 第5大: 6
# 第6大: 7
# 第7大: 8
# 第8大: 不存在