面试题：平衡二叉树

题目描述

输入一棵二叉树，判断该二叉树是否是平衡二叉树。

知识点

平衡二叉树

Qiang的思路

平衡二叉树是指一个二叉树的左子树深度相差不超过1，可以相等或相差为1。

为了判断一个二叉树是不是平衡二叉树，我们只需要计算出左子树和右子树的深度，然后进行对比即可。同样在计算子树深度的时候，我们又需要对每个节点的左右子树进行判断，只要有一个不满足深度差小于1的就说明这个二叉树不是平衡二叉树。

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def judge(self, pRoot):
        if pRoot==None:
            return 0, True
        l,b1=self.judge(pRoot.left)
        r,b2=self.judge(pRoot.right)
        if b1==False or b2==False:
            return 0,False
        if -1<=l-r<=1:
            return max(r,l)+1, True
        return 0, False
    
    def IsBalanced_Solution(self, pRoot):
        # write code here
        _,b=self.judge(pRoot)
        return b

作者原创，如需转载及其他问题请邮箱联系：lwqiang_chn@163.com。
个人网站：https://www.myqiang.top。