Python實(shí)現(xiàn)查找二叉搜索樹(shù)第k大的節(jié)點(diǎn)功能示例
更新時(shí)間：2019年01月24日 10:59:15 作者：hustfc
這篇文章主要介紹了Python實(shí)現(xiàn)查找二叉搜索樹(shù)第k大的節(jié)點(diǎn)功能,結(jié)合實(shí)例形式分析了Python二叉搜索樹(shù)的定義、查找、遍歷等相關(guān)操作技巧,需要的朋友可以參考下
本文實(shí)例講述了Python實(shí)現(xiàn)查找二叉搜索樹(shù)第k大的節(jié)點(diǎn)功能。分享給大家供大家參考，具體如下：
題目描述
給定一個(gè)二叉搜索樹(shù)，找出其中第k大的節(jié)點(diǎn)
就是一個(gè)中序遍歷的過(guò)程，不需要額外的數(shù)組，便利到節(jié)點(diǎn)之后，k減一就行。
代碼1
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def __init__(self):
self.k = 0
def recursionKthNode(self, Root):
result = None
if result == None and Root.left:
result = self.recursionKthNode(Root.left)
if result == None:
if self.k == 1:
return Root
self.k -= 1
if result == None and Root.right:
result = self.recursionKthNode(Root.right)
return result
def KthNode(self, Root, k):
if Root == None:
return None
self.k = k
return self.recursionKthNode(Root)
Root = TreeNode(5)
Root.left = TreeNode(3)
Root.left.left = TreeNode(2)
Root.left.right = TreeNode(4)
Root.right = TreeNode(7)
Root.right.left = TreeNode(6)
Root.right.right = TreeNode(8)
print(Solution().KthNode(Root,3).val)
output : 4
代碼2
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def __init__(self):
self.k = 0
def InOrder(self, Root):
ans = None
if Root:
if ans == None and Root.left:
ans = self.InOrder(Root.left) #往左遍歷
if ans == None and self.k == 1:
ans = Root #遍歷到目標(biāo)節(jié)點(diǎn)
if ans == None and self.k != 1: #沒(méi)有遍歷到目標(biāo)節(jié)點(diǎn)，k--
self.k -= 1
if ans == None and Root.right: #往右遍歷
ans = self.InOrder(Root.right)
return ans
def KthNode(self, Root, k):
if Root == None or k <= 0:
return None
self.k = k
return self.InOrder(Root)
更多關(guān)于Python相關(guān)內(nèi)容感興趣的讀者可查看本站專(zhuān)題：《Python數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Python加密解密算法與技巧總結(jié)》、《Python編碼操作技巧總結(jié)》、《Python函數(shù)使用技巧總結(jié)》、《Python字符串操作技巧匯總》及《Python入門(mén)與進(jìn)階經(jīng)典教程》
希望本文所述對(duì)大家Python程序設(shè)計(jì)有所幫助。
相關(guān)文章
淺談?dòng)肞ython實(shí)現(xiàn)一個(gè)大數(shù)據(jù)搜索引擎
這篇文章主要介紹了淺談?dòng)肞ython實(shí)現(xiàn)一個(gè)大數(shù)據(jù)搜索引擎，小編覺(jué)得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2017-11-11
Python?sklearn庫(kù)中的隨機(jī)森林模型詳解
本文主要說(shuō)明?Python?的?sklearn?庫(kù)中的隨機(jī)森林模型的常用接口、屬性以及參數(shù)調(diào)優(yōu)說(shuō)明,需要讀者或多或少了解過(guò)sklearn庫(kù)和一些基本的機(jī)器學(xué)習(xí)知識(shí)2023-08-08
今天小編就為大家分享一篇淺談tensorflow 中tf.concat()的使用，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2020-02-02
Python3列表List入門(mén)知識(shí)附實(shí)例
序列是Python中最基本的數(shù)據(jù)結(jié)構(gòu)。序列中的每個(gè)元素都分配一個(gè)數(shù)字 - 它的位置，或索引，第一個(gè)索引是0，第二個(gè)索引是1，依此類(lèi)推2020-02-02
python實(shí)現(xiàn)連續(xù)圖文識(shí)別
這篇文章主要為大家詳細(xì)介紹了python實(shí)現(xiàn)連續(xù)圖文識(shí)別功能，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
2018-12-12 
這篇文章主要介紹了Python?matplotlib底層原理，下面文章圍繞Python?matplotlib底層原理的相關(guān)資料展開(kāi)詳細(xì)內(nèi)容,具有一定的參考價(jià)值，需要的朋友可以參考下
2021-12-12 
python 擴(kuò)展print打印文件路徑和當(dāng)前時(shí)間信息的實(shí)例代碼
本文通過(guò)實(shí)例代碼給大家介紹了python 擴(kuò)展print打印文件路徑和當(dāng)前時(shí)間信息,代碼簡(jiǎn)單易懂，非常不錯(cuò)，具有一定的參考借鑒價(jià)值，需要的朋友可以參考下
2019-10-10 
python操作MySQL數(shù)據(jù)庫(kù)的方法分享
堅(jiān)持每天學(xué)一點(diǎn)，每天積累一點(diǎn)點(diǎn)，作為自己每天的業(yè)余收獲，這個(gè)文章是我在吃飯的期間寫(xiě)的，利用自己零散的時(shí)間學(xué)了一下python操作MYSQL，所以整理一下
2012-05-05 
python爬蟲(chóng)教程之bs4解析和xpath解析詳解
這篇文章主要給大家介紹了關(guān)于python爬蟲(chóng)教程之bs4解析和xpath解析的相關(guān)資料,bs4、xpath比較容易上手但是功能有限,正則比較晦澀難懂但是功能超級(jí)強(qiáng)大,需要的朋友可以參考下
2022-02-02