Question 230: Kth Smallest Element in a BST
Difficulty: Medium
題目描述
給定一個二叉搜尋樹，編寫一個函數 kthSmallest 來查找其中第 k 個最小的元素。
說明： 你可以假設 k 總是有效的，1 ≤ k ≤ 二叉搜尋樹元素個數
示例：
輸入: root = [3,1,4,null,2], k = 1 3 / \ 1 4 \ 2輸出: 1
輸入: root = [5,3,6,2,4,null,null,1], k = 3 5 / \ 3 6 / \ 2 4 / 1輸出: 3
題目分析
本題應當注意和之前發過的文章LeetCode每日一題 Q215數組中的第K個最大元素區分開，雖然看起來都是在求第K大(小)的元素，但本題的實質在于利用二叉搜素樹的性質(在下文中有詳細介紹)。二叉搜尋樹的中序周遊排序恰好是本題所需。
關于二叉搜尋樹
二叉搜尋樹(BST)又稱二叉查找樹或二叉排序樹。一棵二叉搜尋樹是以二叉樹來組織的，可以使用一個連結清單資料結構來表示，其中每一個結點就是一個對象。一般地，除了key和衛星資料之外，每個結點還包含屬性lchild、rchild和parent，分别指向結點的左孩子、右孩子和雙親(父結點)。如果某個孩子結點或父結點不存在，則相應屬性的值為空(NIL)。根結點是樹中唯一父指針為NIL的結點，而葉子結點的孩子結點指針也為NIL。
二叉搜尋樹的性質
設x是二叉搜尋樹中的一個結點。如果y是x左子樹中的一個結點，那麼y.key≤x.key。如果y是x右子樹中的一個結點，那麼y.key ≥ x.key。在二叉搜尋樹中：
•若任意結點的左子樹不空，則左子樹上所有結點的值均不大于它的根結點的值。•若任意結點的右子樹不空，則右子樹上所有結點的值均不小于它的根結點的值。•任意結點的左、右子樹也分别為二叉搜尋樹。
二叉搜尋樹的三種周遊方式
•前序周遊(pre-order)•中序周遊(in-order)•後續周遊(post-order)
DFS解法
//Java 解法class Solution { int counter = 0; int Kmin; public int kthSmallest(TreeNode root, int k) { inOrder(root, k); return Kmin; } public void inOrder(TreeNode root, int k){ if(root.left != null) { inOrder(root.left, k); } if(++counter == k){ Kmin = root.val; } if(root.right != null){ inOrder(root.right, k); } }}
#python 解法class Solution: def kthSmallest(self, root, k): """ :type root: TreeNode :type k: int :rtype: int """ def inorder(r): return inorder(r.left) + [r.val] + inorder(r.right) if r else [] return inorder(root)[k - 1]
BFS解法
// JAVA 解法class Solution { public int kthSmallest(TreeNode root, int k) { LinkedList<TreeNode> stack = new LinkedList<TreeNode>(); while (true) { while (root != null) { stack.add(root); root = root.left; } root = stack.removeLast(); if (--k == 0) return root.val; root = root.right; } }}
# Python 解法class Solution: def kthSmallest(self, root, k): """ :type root: TreeNode :type k: int :rtype: int """ stack = [] while True: while root: stack.append(root) root = root.left root = stack.pop() k -= 1 if not k: return root.val root = root.right