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

本文实例讲述了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程序设计有所帮助。

时间: 2019-01-22

Python数据结构之双向链表的定义与使用方法示例

本文实例讲述了Python数据结构之双向链表的定义与使用方法.分享给大家供大家参考,具体如下: 和单链表类似,只不过是增加了一个指向前面一个元素的指针而已. 示意图: python 实现代码: #!/usr/bin/python # -*- coding: utf-8 -*- class Node(object): def __init__(self,val,p=0): self.data = val self.next = p self.prev = p class LinkList(obje

Python实现的序列化和反序列化二叉树算法示例

本文实例讲述了Python实现的序列化和反序列化二叉树算法.分享给大家供大家参考,具体如下: 题目描述 请实现两个函数,分别用来序列化和反序列化二叉树 序列化二叉树 先序遍历二叉树 def recursionSerialize(self, root): series = '' if root == None: series += ',$' else: series += (',' + str(root.val)) series += self.recursionSerialize(root.le

python双向链表实现实例代码

示意图: python双向链表实现代码: 复制代码 代码如下: #!/usr/bin/python# -*- coding: utf-8 -*- class Node(object):    def __init__(self,val,p=0):        self.data = val        self.next = p        self.prev = p class LinkList(object):    def __init__(self):        self.he

Python二叉树的遍历操作示例【前序遍历,中序遍历,后序遍历,层序遍历】

本文实例讲述了Python二叉树的遍历操作.分享给大家供大家参考,具体如下: # coding:utf-8 """ @ encoding: utf-8 @ author: lixiang @ email: lixiang_cn@foxmail.com @ python_version: 2 @ time: 2018/4/11 0:09 @ more_info: 二叉树是有限个元素的集合,该集合或者为空.或者有一个称为根节点(root)的元素及两个互不相交的.分别被称为左子树和

Python单向链表和双向链表原理与用法实例详解

本文实例讲述了Python单向链表和双向链表原理与用法.分享给大家供大家参考,具体如下: 链表是一种数据结构,链表在循环遍历的时候效率不高,但是在插入和删除时优势比较大. 链表由一个个节点组成. 单向链表的节点分为两个部分:存储的对象和对下一个节点的引用.注意是指向下一个节点. 而双向链表区别于单向链表的是它是由三个部分组成:存储的对象.对下一个节点的引用.对上一个节点的引用,可以实现双向遍历. 单向列表的结构如下图: head是头节点,tail是尾节点,每个节点由Data存储对象和Next对下

Python实现二叉搜索树

二叉搜索树 我们已经知道了在一个集合中获取键值对的两种不同的方法.回忆一下这些集合是如何实现ADT(抽象数据类型)MAP的.我们讨论两种ADT MAP的实现方式,基于列表的二分查找和哈希表.在这一节中,我们将要学习二叉搜索树,这是另一种键指向值的Map集合,在这种情况下我们不用考虑元素在树中的实际位置,但要知道使用二叉树来搜索更有效率. 搜索树操作 在我们研究这种实现方式之前,让我们回顾一下ADT MAP提供的接口.我们会注意到,这种接口和Python的字典非常相似. Map() 创建了一个新的

Python二叉搜索树与双向链表转换算法示例

本文实例讲述了Python二叉搜索树与双向链表转换算法.分享给大家供大家参考,具体如下: 题目描述 输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表.要求不能创建任何新的结点,只能调整树中结点指针的指向. 普通的二叉树也可以转换成双向链表,只不过不是排序的 思路: 1. 与中序遍历相同 2. 采用递归,先链接左指针,再链接右指针 代码1,更改doubleLinkedList,最后返回list的第一个元素: class TreeNode: def __init__(self, x): s

Python二叉搜索树与双向链表转换实现方法

本文实例讲述了Python二叉搜索树与双向链表实现方法.分享给大家供大家参考,具体如下: # encoding=utf8 ''' 题目:输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表. 要求不能创建任何新的结点,只能调整树中结点指针的指向. ''' class BinaryTreeNode(): def __init__(self, value, left = None, right = None): self.value = value self.left = left self.

Python双向循环链表实现方法分析

本文实例讲述了Python双向循环链表实现方法.分享给大家供大家参考,具体如下: 最近身边的朋友在研究用python来实现数据结构.遇到一个问题就是双向循环链表的实现,改指向的时候总是发蒙. 我自己尝实现了一个python的双向循环链表.附上代码,希望对大家有帮助. 如果不懂什么是双向循环链表的伙伴,需要补习一下数据结构的基础之后哦~~~ 在python当中 用一个类Node 来实现链表的节点,节点数据有三个变量: prev:前驱指针: 用于指向当前节点前一个节点 next: 后继指针  用于指

Python字符串格式化输出方法分析

本文实例分析了Python字符串格式化输出方法.分享给大家供大家参考,具体如下: 我们格式化构建字符串可以有3种方法: 1 元组占位符 m = 'python' astr = 'i love %s' % m print astr 2 字符串的format方法 m = 'python' astr = "i love {python}".format(python=m) print astr 3 字典格式化字符串 m = 'python' astr = "i love %(pyt

python中类的一些方法分析

本文实例分析了python中类的一些方法,分享给大家供大家参考.具体分析如下: 先来看看下面这段代码: class Super: def delegate(self): self.action() class Provider(Super): def action(self): print 'in Provider.action' x = Provider() x.delegate() 本文实例运行环境为Python2.7.6 运行结果如下: in Provider.action 在Super类

python UNIX_TIMESTAMP时间处理方法分析

本文实例讲述了python UNIX_TIMESTAMP时间处理方法.分享给大家供大家参考,具体如下: from datetime import datetime import time int(time.mktime(rm.start_time.timetuple())) datetime.fromtimestamp(time.time()) rf.start_time + timedelta(0, math.ceil(diff.total_seconds()/(3600*rf.period)

Python表示矩阵的方法分析

本文实例讲述了Python表示矩阵的方法.分享给大家供大家参考,具体如下: 在c语言中,表示个"整型3行4列"的矩阵,可以这样声明:int  a[3][4];在python中一不能声明变量int,二不能列出维数.可以利用列表中夹带列表形式表示.例如: 表示矩阵 ,可以这样: count = 1 a = [] for i in range(0, 3): tmp = [] for j in range(0, 3): tmp.append(count) count += 1 a.append

Python字符编码判断方法分析

本文实例讲述了Python字符编码判断方法.分享给大家供大家参考,具体如下: 方法一: isinstance(s, str) 用来判断是否为一般字符串 isinstance(s, unicode) 用来判断是否为unicode 或 if type(str).__name__!="unicode": str=unicode(str,"utf-8") else: pass 方法二: Python chardet 字符编码判断 使用 chardet 可以很方便的实现字符串

python创建子类的方法分析

本文实例讲述了python创建子类的方法.分享给大家供大家参考,具体如下: 如果你的类没有从任何祖先类派生,可以使用object作为父类的名字.经典类的声明唯一不同之处在于其没有从祖先类派生---此时,没有圆括号: # !/usr/bin/env python # -*- coding: utf-8 -*- class ClassicClassWithoutSuperclasses: def fun1(self): print 'aaaaaaa' a=ClassicClassWithoutSup

js实现视图和数据双向绑定的方法分析

本文实例讲述了js实现视图和数据双向绑定的方法.分享给大家供大家参考,具体如下: 前言 视图和数据绑定,使视图和逻辑层分离,使视图层变为数据驱动是前端的一大进步.由此诞生了mvvm类的前端框架,大大提升了开发的效率. 那么在使用旧有的项目中,如何使用更加先进的设计模式来替换掉大量的面向过程编程. 各大框架对于数据绑定的实现都有各自的方式,这里不做深入只是简单介绍一下. Vue使用了es5  Object.defineProperty的特性来实现对数据读取和设置的监听,是一种元编程的方式.个人感觉

python实现数据结构中双向循环链表操作的示例

看此博客之前建议先看看B站的视频python数据结构与算法系列课程,该课程中未实现双向循环链表的操作,所以我按照该视频的链表思路实现了双向循环链表的操作,欢迎大家阅读与交流,如有侵权,请联系博主! 下面附上代码: class Node: def __init__(self, elem): self.elem = elem self.prev = None self.next = None class DoubleCycleLinkList: def __init__(self, node=Non

Python类的专用方法实例分析

本文实例讲述了Python类的专用方法.分享给大家供大家参考.具体分析如下: Python 类可以定义专用方法,专用方法是在特殊情况下或当使用特别语法时由 Python 替你调用的,而不是在代码中直接调用(象普通的方法那样). 1. __init__ 类似于构造函数 复制代码 代码如下: #!/usr/local/bin/python class Study:         def __init__(self,name=None):                 self.name = na