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

注意在使用递归时不要考虑进深层次，设置好基准情形就好。