算法题 19 二叉平衡树检查牛客网 CC150

实现一个函数，检查二叉树是否平衡，平衡的定义如下，对于树中的任意一个结点，其两颗子树的高度差不超过1。

给定指向树根结点的指针TreeNode* root，请返回一个bool，代表这棵树是否平衡。

解题代码：时间复杂度为O(NlogN) N为树中的节点数

# -*- coding:utf-8 -*-

# class TreeNode:

#     def __init__(self, x):

#         self.val = x

#         self.left = None

#         self.right = None

class Balance:

    def isBalance(self, root):

        # write code here

        if not root:

            return True

        heightDiff=self.getHeight(root.left)-self.getHeight(root.right)

        if abs(heightDiff)>1:

            return False

        else:

            return self.isBalance(root.left) and self.isBalance(root.right)

    def getHeight(self,root):

        if not root:

            return 0

        return max(self.getHeight(root.left),self.getHeight(root.right))+1

解题代码二：优化版，时间复杂度为O(N),空间复杂度为O(H)，H为树的高度

# -*- coding:utf-8 -*-

# class TreeNode:

#     def __init__(self, x):

#         self.val = x

#         self.left = None

#         self.right = None

class Balance:

    def isBalance(self, root):

        # write code here

        if self.checkHeight(root)==-1:

            return False

        else:

            return True

    def checkHeight(self,root):

        if not root:

            return 0 #高度为0

        leftHeight=self.checkHeight(root.left)

        if leftHeight==-1:

            return -1 # 不平衡

        rightHeight=self.checkHeight(root.right)

        if rightHeight==-1:

            return -1 # 不平衡

        heightDiff=leftHeight-rightHeight

        if abs(heightDiff)>1:

            return -1

        else:

            return max(leftHeight,rightHeight)+1

巴特西

算法题 19 二叉平衡树检查牛客网 CC150

最新文章

热门文章

巴特西

算法题 19 二叉平衡树检查 牛客网 CC150

最新文章

热门文章

算法题 19 二叉平衡树检查牛客网 CC150