Python:递归解决求二叉查找树高度

>>最全面的Java面试大纲及答案解析(建议收藏)  

二叉查找树的高度

二叉查找树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:递归解决求二叉查找树高度