題目描述

給定一個(gè)二叉搜索樹(shù)，編寫(xiě)一個(gè)函數(shù) kthSmallest 來(lái)查找其中第 k 個(gè)最小的元素。

說(shuō)明：
你可以假設(shè) k 總是有效的，1 ≤ k ≤ 二叉搜索樹(shù)元素個(gè)數(shù)。

示例 1:

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

示例 2:

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

進(jìn)階：
如果二叉搜索樹(shù)經(jīng)常被修改（插入/刪除操作）并且你需要頻繁地查找第 k 小的值，你將如何優(yōu)化 kthSmallest 函數(shù)？

---

解題思路

二叉搜索樹(shù)（BST）是一棵二叉樹(shù)，每個(gè)節(jié)點(diǎn)的值都大于其左子樹(shù)中的任意節(jié)點(diǎn)的的值而小于右子樹(shù)的任意節(jié)點(diǎn)的值。

翻閱了一下《算法》第四版的相關(guān)章節(jié)，發(fā)現(xiàn)樹(shù)上的二叉樹(shù)維護(hù)了一個(gè)N來(lái)記錄以當(dāng)前節(jié)點(diǎn)為根節(jié)點(diǎn)的子樹(shù)的節(jié)點(diǎn)總數(shù)。通過(guò)N，我們就可以從上往下遍歷二叉搜索樹(shù)時(shí)，選擇往左走還是往右走，直到找到我們要找的節(jié)點(diǎn)。具體方式如下：

假設(shè)我們想找到第k小的元素（即樹(shù)中正好有k-1個(gè)小于它的值），如果左子樹(shù)中的節(jié)點(diǎn)數(shù)t > k-1，那我們就繼續(xù)（遞歸地）在左子樹(shù)中搜索第k小的元素；如果t = k-1我們就返回該節(jié)點(diǎn)的值；如果t < k-1，我們就（遞歸地）在右子樹(shù)中查找第k-t-1小的值。

現(xiàn)在我們需要一個(gè)統(tǒng)計(jì)N的方法private int size (TreeNode root)，可以用遞歸的方式來(lái)實(shí)現(xiàn)，每個(gè)節(jié)點(diǎn)的N等于該節(jié)點(diǎn)的左子樹(shù)的N+該節(jié)點(diǎn)的右子樹(shù)的N+1，這個(gè) 1 就是該節(jié)點(diǎn)。

源代碼

public int kthSmallest (TreeNode root, int k) {int t = size(root.left);if (t > k - 1) return kthSmallest(root.left, k);else if (t < k - 1) return kthSmallest(root.right, k - t - 1);else return root.val;
}private int size (TreeNode root) {if (root == null) return 0;return size(root.left) + size(root.right) + 1;
}

心得體會(huì)

這一題是二叉搜索樹(shù)，而不是簡(jiǎn)單的二叉樹(shù)，所以要利用二叉搜索樹(shù)的特點(diǎn)來(lái)找到解題思路。

轉(zhuǎn)載于:https://www.cnblogs.com/yuzhenzero/p/10275561.html

總結(jié)

以上是生活随笔為你收集整理的【LeetCode】230#二叉搜索树中第K小的元素的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。