[剑指Offer] 54_二叉搜索树的第K大节点

题目

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

例：

如下图的二叉搜索树，按节点数值大小顺序，第三大节点是4。
        5
       / \
      3   7
     / \ / \
    2  4 6  8
           

思路

1. 题目表述有误，按照其例子应为第K小节点。因为是二叉搜索树，因此节点大小是有规律的，以LDR中序序遍历的第K个节点就是第K小节点。
   1. 时间复杂度：O(n)
   2. 空间复杂度：O(logn)

代码

思路1：时间复杂度：O(n)，空间复杂度：O(logn)

def kth_node_in_BST(root, k):
    """
    :param root: Binary Search Tree root
    :param k: kth smallest
    :return: kth smallest node
    """

    def recursion(root, k):
        nonlocal target
        if not root:
            return k
        k = recursion(root.left, k)
        if not target:
            if k == 1:
                target = root
            else:
                k -= 1
        if not target:
            k = recursion(root.right, k)
        return k
    target = None
    recursion(root, k)
    return target
           

思考

相同的题目

LeetCode 230. 二叉搜索树中第K小的元素

题目

给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。

说明：

你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。

示例 1:

输入: root = [3,1,4,null,2], k = 1
   3
  / \
 1   4
  \
   2
输出: 1
           

示例 2:

输入: root = [5,3,6,2,4,null,null,1], k = 3
       5
      / \
     3   6
    / \
   2   4
  /
 1
输出: 3
           

进阶：

如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化 kthSmallest 函数？

代码

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def kthSmallest(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: int
        """
        ans = None
        flag = False
        def search(root,k):
            nonlocal ans
            nonlocal flag
            if flag:
                return 0
            if not root:
                return 0
            count_min = search(root.left, k) + 1
            if  count_min == k:
                flag = True
                ans = root
            r = search(root.right, k - count_min)           
            return count_min + r
        search(root,k)
        return ans.val
           

上面的代码和正文中不一样，返回值为计数，用flag和ans来表征和记录target。看起来比较绕，没有后来写得好。