Python:递归解决求二叉查找树高度
二叉查找树的高度
二叉查找树(BST,binary search tree)是一种很重要的数据结构。树(tree)的高(height)定义为树的根(root)到一片树叶的最长路径的长。
解决
树的问题很适合用递归
解决。求树的高,相当于要对树做遍历。
首先写一个节点类:
class Node:
def __init__(self,data):
self.right=self.left = None
self.data = data
接着是构造二叉查找树:
class Solution:
def insert(self,root,data):
if root == None:
return Node(data)
else:
if data <= root.data:
cur = self.insert(root.left,data)
root.left = cur
else:
cur = self.insert(root.right,data)
root.right = cur
return root
def getHeight(self,root):
pass
最后就是问题的解决了:
def getHeight(self,root):
if root is None:
return -1
else:
return max(self.getHeight(root.left), self.getHeight(root.right)) + 1
注意在使用递归
时不要考虑进深层次,设置好基准情形
就好。
原文始发于微信公众号(公子政的宅日常):Python:递归解决求二叉查找树高度