剑指offer——python【第39题】平衡二叉树

题目描述

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

 

解题思路

平衡二叉树首先是二叉搜索树，且它每个节点的左子树和右子树高度差至多等于1；只要从根节点，依次递归判断每个节点是否满足如上条件即可；那么可以首先构造一个求任意节点树深的函数TreeDepth，然后取左右子树的深度差的绝对值，判断是否大于1；然后递归判断左子树和右子树的每个节点，如果都小于等于1的话，则为平衡二叉树

代码

class Solution:

    def TreeDepth(self,pRoot):

        if pRoot is None:

            return 0

        lDepth = self.TreeDepth(pRoot.left)

        rDepth = self.TreeDepth(pRoot.right)

        return max(lDepth,rDepth)+1

    def IsBalanced_Solution(self, pRoot):

        # write code here

        if pRoot is None:

            return True

        right = self.TreeDepth(pRoot.right)

        left = self.TreeDepth(pRoot.left)

        if abs(right-left)>1:

            return False

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