剑指offer 平衡二叉树

佚名 6年前 (2019-04-10) 随笔 281人围观抢沙发百度已收录

# -*- coding: utf-8 -*-
"""
Created on Wed Apr 10 09:59:37 2019

@author: Administrator
题目：
输入一棵二叉树，判断该二叉树是否是平衡二叉树。
思路：
从平衡二叉树的定义入手,：
step1：左子树和右子树的高度差的绝对值不能超过1
step2：左子树和右子树也是平衡二叉树
我们写两个函数，返回其树的高度，比较是否高度差小于1，其次递归调用左右子树
"""

# -*- coding:utf-8 -*-
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
        if not pRoot:                       #空数为平衡二叉树
            return True
        left = self.TreeDepth(pRoot.left)   #得到左子树的高度
        right = self.TreeDepth(pRoot.right) #得到右子树的高度
        if abs(left - right) > 1:           #比较左右子树的高度差
            return False                    #若大于1，就不是平衡二叉树
                                            #再递归调用左右子树，也是平衡二叉树，用and
        return self.IsBalanced_Solution(pRoot.left) and self.IsBalanced_Solution(pRoot.right)
                                            #函数，返回其树的深度
    def TreeDepth(self,pRoot):
        if not pRoot:                       #如果为空节点就返回0
            return 0
        left = self.TreeDepth(pRoot.left)   #得到左子树的高度
        right = self.TreeDepth(pRoot.right) #得到右子树的高度
        return max(left+1,right+1)          #返回高度叠加
if __name__ == '__main__':
    solution = Solution()
    
    #1 2 3 4 5 6 7 8 9
    n = TreeNode(9)
    node = TreeNode(8)
    node_left = TreeNode(1)
    node_right = TreeNode(3)
    node.left = n
    node_left.left = node
    root_left = TreeNode(2)
    root_left.left = node_left
    root_left.right = node_right
    
    node_left = TreeNode(5)
    node_right = TreeNode(7)
    root_right = TreeNode(6)
    root = TreeNode(4)
    root.left = root_left
    root_right.left = node_left
    root_right.right = node_right
    root.right = root_right
    
    res = solution.IsBalanced_Solution(root)
    print(res)                              #这个不是平衡二叉树，因为左子树高度为2，右子树为0