溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本文實例講述了Python實現查找二叉搜索樹第k大的節點功能。分享給大家供大家參考，具體如下：
題目描述
給定一個二叉搜索樹，找出其中第k大的節點
就是一個中序遍歷的過程，不需要額外的數組，便利到節點之后，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 #遍歷到目標節點
if ans == None and self.k != 1: #沒有遍歷到目標節點，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)
更多關于Python相關內容感興趣的讀者可查看本站專題：《Python數據結構與算法教程》、《Python加密解密算法與技巧總結》、《Python編碼操作技巧總結》、《Python函數使用技巧總結》、《Python字符串操作技巧匯總》及《Python入門與進階經典教程》
希望本文所述對大家Python程序設計有所幫助。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
