劍指 Offer 54. 二叉搜索樹的第k大節(jié)點

給定一棵二叉搜索樹，請找出其中第k大的節(jié)點。

示例 1:

輸入: root = [3,1,4,null,2], k = 1

? ?3

? / \

?1? ?4

? \

? ?2

輸出: 4

示例 2:

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

? ? ? ?5

? ? ? / \

? ? ?3? ?6

? ? / \

? ?2? ?4

? /

?1

輸出: 4

題目解析

二叉查找樹（英語：Binary Search Tree），也稱為 二叉搜索樹、有序二叉樹（Ordered Binary Tree）或排序二叉樹（Sorted Binary Tree），是指一棵空樹或者具有下列性質(zhì)的二叉樹：

若任意節(jié)點的左子樹不空，則左子樹上所有節(jié)點的值均小于它的根節(jié)點的值；

若任意節(jié)點的右子樹不空，則右子樹上所有節(jié)點的值均大于它的根節(jié)點的值；

任意節(jié)點的左、右子樹也分別為二叉查找樹；

沒有鍵值相等的節(jié)點。

二叉查找樹相比于其他數(shù)據(jù)結(jié)構(gòu)的優(yōu)勢在于查找、插入的時間復(fù)雜度較低。為 O(logn)。二叉查找樹是基礎(chǔ)性數(shù)據(jù)結(jié)構(gòu)，用于構(gòu)建更為抽象的數(shù)據(jù)結(jié)構(gòu)，如集合、多重集、關(guān)聯(lián)數(shù)組等。

二叉查找樹的查找過程和次優(yōu)二叉樹類似，通常采取二叉鏈表作為二叉查找樹的存儲結(jié)構(gòu)。中序遍歷二叉查找樹可得到一個關(guān)鍵字的有序序列，一個無序序列可以通過構(gòu)造一棵二叉查找樹變成一個有序序列，構(gòu)造樹的過程即為對無序序列進行查找的過程。每次插入的新的結(jié)點都是二叉查找樹上新的葉子結(jié)點，在進行插入操作時，不必移動其它結(jié)點，只需改動某個結(jié)點的指針，由空變?yōu)榉强占纯伞Ｋ阉?、插入、刪除的復(fù)雜度等于樹高，期望 O(logn)，最壞 O(n)（數(shù)列有序，樹退化成線性表）。

雖然二叉查找樹的最壞效率是 O(n)，但它支持動態(tài)查詢，且有很多改進版的二叉查找樹可以使樹高為 O(logn)，從而將最壞效率降至 O(logn)，如 AVL 樹、紅黑樹等。

題目解答

代碼展示

# Definition for a binary tree node.# class TreeNode:#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = None
class Solution:    def kthLargest(self, root: TreeNode, k: int) -> int:        '''            方法：遞歸法            思路：                右->根->左 遍歷        '''        self.k = k        self.dfs(root)         return self.res
    def dfs(self,root):        if not root:            return         self.dfs(root.right)        if self.k==0:            return             self.k = self.k-1        if self.k==0:            self.res = root.val        self.dfs(root.left)

復(fù)雜度計算

• 時間復(fù)雜度 O(N)：當(dāng)樹退化為鏈表時（全部為右子節(jié)點），無論 k 的值大小，遞歸深度都為 N ，占用 O(N) 時間。

• 空間復(fù)雜度 O(N) ：當(dāng)樹退化為鏈表時（全部為右子節(jié)點），系統(tǒng)使用 O(N)大小的?？臻g。

運行結(jié)果