python判断平衡二叉树

题目：输入一棵二叉树，判断该二叉树是否是平衡二叉树。若左右子树深度差不超过1则为一颗平衡二叉树。
思路：

使用获取二叉树深度的方法来获取左右子树的深度
左右深度相减，若大于1返回False
通过递归对每个节点进行判断，若全部均未返回False，则返回True

class TreeNode():

    def __init__(self,x):

        self.val  = x

        self.left = None

        self.right = None

class Solution:

    def getDeepth(self,Root):

        if Root is None:

            return 0

        nright = self.getDeepth(Root.right)

        nleft = self.getDeepth(Root.left)

        return max(nright,nleft)+1

    def IsBalance_solution(self,pRoot):

        if pRoot is None:

            return True

        right = self.getDeepth(pRoot.right)

        left = self.getDeepth(pRoot.left)

        if abs(right - left) > 1:

            return False

        return self.IsBalance_solution(pRoot.right) and self.IsBalance_solution(pRoot.left)

巴特西

python判断平衡二叉树

最新文章

热门文章