Python實(shí)現(xiàn)查找二叉搜索樹第k大的節(jié)點(diǎn)功能示例

更新時間：2019年01月24日 10:59:15 作者：hustfc

這篇文章主要介紹了Python實(shí)現(xiàn)查找二叉搜索樹第k大的節(jié)點(diǎn)功能,結(jié)合實(shí)例形式分析了Python二叉搜索樹的定義、查找、遍歷等相關(guān)操作技巧,需要的朋友可以參考下

本文實(shí)例講述了Python實(shí)現(xiàn)查找二叉搜索樹第k大的節(jié)點(diǎn)功能。分享給大家供大家參考，具體如下：

題目描述

給定一個二叉搜索樹，找出其中第k大的節(jié)點(diǎn)

就是一個中序遍歷的過程，不需要額外的數(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:   #沒有遍歷到目標(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)容感興趣的讀者可查看本站專題：《Python數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Python加密解密算法與技巧總結(jié)》、《Python編碼操作技巧總結(jié)》、《Python函數(shù)使用技巧總結(jié)》、《Python字符串操作技巧匯總》及《Python入門與進(jìn)階經(jīng)典教程》

希望本文所述對大家Python程序設(shè)計(jì)有所幫助。

您可能感興趣的文章: