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

更新時(shí)間：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)功能。分享給大家供大家參考，具體如下：

題目描述

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

就是一個(gè)中序遍歷的過程，不需要額外的數(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)典教程》

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

您可能感興趣的文章:

相關(guān)文章

淺談?dòng)肞ython實(shí)現(xiàn)一個(gè)大數(shù)據(jù)搜索引擎
這篇文章主要介紹了淺談?dòng)肞ython實(shí)現(xiàn)一個(gè)大數(shù)據(jù)搜索引擎，小編覺得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧
2017-11-11
Python?sklearn庫中的隨機(jī)森林模型詳解
本文主要說明?Python?的?sklearn?庫中的隨機(jī)森林模型的常用接口、屬性以及參數(shù)調(diào)優(yōu)說明,需要讀者或多或少了解過sklearn庫和一些基本的機(jī)器學(xué)習(xí)知識(shí)
2023-08-08
淺談tensorflow 中tf.concat()的使用
今天小編就為大家分享一篇淺談tensorflow 中tf.concat()的使用，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧
2020-02-02
Python3列表List入門知識(shí)附實(shí)例
序列是Python中最基本的數(shù)據(jù)結(jié)構(gòu)。序列中的每個(gè)元素都分配一個(gè)數(shù)字 - 它的位置，或索引，第一個(gè)索引是0，第二個(gè)索引是1，依此類推
2020-02-02
本文詳細(xì)講解了Python的面向?qū)ο缶幊?，文中通過示例代碼介紹的非常詳細(xì)。對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下
2022-05-05