Skip to content

230 kth smallest element in a bst

230. Kth Smallest Element in a BST

题目: https://leetcode.com/problems/kth-smallest-element-in-a-bst/

难度: Medium

跟昨天做的一道题类似,一上来就走取巧之路。

InOrder排序,输出,当然也完全可以用昨天的binary tree iterator,入stack,出stack,直到输出第k位

class Solution(object):
    def kthSmallest(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: int
        """
        self.root = root
        self.lst = []
        self.inOrder(root)
        return self.lst[k-1]

    def inOrder(self, root):
        if root == None:
            return
        self.inOrder(root.left)
        self.lst.append(root.val)
        self.inOrder(root.right)

现在看到kth 就条件反射的想用divide & conquer, 扫root的左子树看nodes量,如果nodes数量是k-1,那么node就刚好是第k个,如果大于k > 左子树数量,扫右子树,同时更新root为root.right。

看到的言论:

If we can change the BST node structure, We can add a new Integer to mark the number of element in the left sub-tree.

when the node is not null.

  • if k == node.leftNum + 1, return node
  • if k > node.leftNum + 1, make k -= node.leftNum + 1, and then node = node.right
  • otherwise, node = node.left


回到顶部