Python实现查找二叉搜索树第k大的节点功能示例-创新互联

本文实例讲述了Python实现查找二叉搜索树第k大的节点功能。分享给大家供大家参考,具体如下:

成都创新互联公司是一家集网站建设,保定企业网站建设,保定品牌网站建设,网站定制,保定网站建设报价,网络营销,网络优化,保定网站推广为一体的创新建站企业,帮助传统企业提升企业形象加强企业竞争力。可充分满足这一群体相比中小企业更为丰富、高端、多元的互联网需求。同时我们时刻保持专业、时尚、前沿,时刻以成就客户成长自我,坚持不断学习、思考、沉淀、净化自己,让我们为更多的企业打造出实用型网站。创新互联公司专注于环县网站建设服务及定制,我们拥有丰富的企业做网站经验。 热诚为您提供环县营销型网站建设,环县网站制作、环县网页设计、环县网站官网定制、微信小程序服务,打造环县网络公司原创品牌,更为您提供环县网站排名全网营销落地服务。

题目描述

给定一个二叉搜索树,找出其中第k大的节点

Python实现查找二叉搜索树第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)


当前名称:Python实现查找二叉搜索树第k大的节点功能示例-创新互联
转载来源:http://myzitong.com/article/cehcgd.html