Python二叉搜索树的第k个结点
中序遍历输出一个序列,然后找到序列中第k个数即可。
- '''
- 给定一颗二叉搜索树,请找出其中的第k大的结点。例如,
- 5
- / \
- 3 7
- /\ /\
- 2 4 6 8 中,
- 按结点数值大小顺序第三个结点的值为4。
- '''
-
- # -*- coding:utf-8 -*-
- class TreeNode:
- def __init__(self, x):
- self.val = x
- self.left = None
- self.right = None
- class Solution:
- # 返回对应节点TreeNode
- def __init__(self):
- self.treeNode = []
- def inOrder(self, pRoot):
- if len(self.treeNode) < 0:
- return None
- if pRoot.left:
- self.inOrder(pRoot.left)
- self.treeNode.append(pRoot)
- if pRoot.right:
- self.inOrder(pRoot.right)
- def KthNode(self, pRoot, k):
- if k == 0 or pRoot == None:
- return
- self.inOrder(pRoot)
- if len(self.treeNode) < k:
- return None
- return self.treeNode[k-1]
-
- def KthNode2(self, pRoot, k):
- if k <= 0 or not pRoot:
- return None
- treeStack, nodesQue = [], []
- pNode = pRoot
- while pNode or len(treeStack):
- while pNode:
- treeStack.append(pNode)
- pNode = pNode.left
- if len(treeStack):
- pNode = treeStack.pop()
- nodesQue.append(pNode)
- pNode = pNode.right
- if k > len(nodesQue):
- return None
- return nodesQue[k-1]
解压密码: detechn或detechn.com
免责声明
本站所有资源出自互联网收集整理,本站不参与制作,如果侵犯了您的合法权益,请联系本站我们会及时删除。
本站发布资源来源于互联网,可能存在水印或者引流等信息,请用户自行鉴别,做一个有主见和判断力的用户。
本站资源仅供研究、学习交流之用,若使用商业用途,请购买正版授权,否则产生的一切后果将由下载用户自行承担。