[nowcoder]平衡二叉树

题目描述

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

题目链接: https://www.nowcoder.com/practice/8b3b95850edb4115918ecebdf1b4d222

分析

  1. 递归:如果当前结点为空,返回平衡判断True以及深度0;
  2. 如果左右平衡判断出现False,则返回False;
  3. 如果左右子树的深度差值大于1,则返回False;
  4. 否则返回平衡判断True以及深度(左右子树最大深度+1)

参考代码

class TreeNode:
def __init__(self, x):
    self.val = x
    self.left = None
    self.right = None

class Solution:
def IsBalanced_Solution(self, pRoot):
    # write code here
    def judge(root):
        if(not root):
            return [True,0]
        left_judge,left=judge(root.left)
        right_judge,right=judge(root.right)
        if(not left_judge or not right_judge):
            return [False,0]
        if(abs(left-right)>1):
            return [False,0]
        return [True,max(left,right)+1]
    [bo,dep]=judge(pRoot)
    return bo

运行时间: 21 ms