专栏首页蛮三刀的后端开发专栏[Leetcode][python]Balanced Binary Tree/平衡二叉树

[Leetcode][python]Balanced Binary Tree/平衡二叉树

题目大意

判断一颗二叉树是否是“高度”平衡的。 平衡二叉树的定义是二叉树的任意节点的两颗子树之间的高度差小于等于1。 这实际上是AVL树(维基百科)的定义。

解题思路

递归判断自身和以及自身左右子树是否都是平衡的。 而每个循环内判断的依据就是判断树的深度,之前做过的。

代码

class Solution(object):
    def maxDepth(self, root):
        if root == None:
            return 0
        return max(self.maxDepth(root.left), self.maxDepth(root.right))+1

    def isBalanced(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if root == None:
            return True
        if abs(self.maxDepth(root.left) - self.maxDepth(root.right)) > 1:
            return False
        return self.isBalanced(root.left) and self.isBalanced(root.right)

总结

and/or的用法要牢记,不仅仅是用在if判断里。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • [Leetcode][python]Symmetric Tree/对称二叉树

    其中左子树和右子树对称的条件: 两个节点值相等,或者都为空 左节点的左子树和右节点的右子树对称 左节点的右子树和右节点的左子树对称

    后端技术漫谈
  • [Leetcode][python]二叉树的直径

    https://leetcode-cn.com/problems/diameter-of-binary-tree/description/

    后端技术漫谈
  • [Leetcode][python]Populating Next Right Pointers in Each Node I and II/填充同一层的兄弟节点

    为二叉树的节点都添加一个next指针,指向跟它在同一高度的右边的节点,如果右边没有节点,就指向None。

    后端技术漫谈
  • 剑指offer【30~39】

    除了存储数据的栈 stack,再定义一个最小栈 minstack。minstack 的长度和 stack 保持同步,只不过其是一个递减栈。如 stack = [...

    echobingo
  • WKWebView常见功能及如何返回上级界面

    czjwarrior
  • Python学习之GUI--登录系统界面篇

    tkinker包:Python2.5之后,tkinker包是自带的,我们直接导入就好了

    明天依旧可好
  • pygame系列_箭刺Elephant游戏_源码下载

    http://www.pygame.org/docs/tut/chimp/ChimpLineByLine.html

    Hongten
  • MJRefresh 源码阅读

    用户2215591
  • python pyqt5 pandas处理数据

    """ Module implementing MainWindow. """

    用户5760343
  • Python之pygame学习精灵碰撞做一个躲避球游戏(13)

    获取鼠标返回的坐标,用这个坐标来画圆的时候,设置好不能超出边框,结果圆居然能出去????

    萌海无涯

扫码关注云+社区

领取腾讯云代金券