剑指offer 平衡二叉树

Posted on |

平衡二叉树

题目

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

方法

方法1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# -*- 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_height=self.getHeight(pRoot.left)
        right_height=self.getHeight(pRoot.right)
        if abs(left_height-right_height)>1:
            return False
        return self.IsBalanced_Solution(pRoot.left) and self.IsBalanced_Solution(pRoot.right)

    def getHeight(self,node):
        if not node:
            return 0
        left=self.getHeight(node.left)
        right=self.getHeight(node.right)
        return 1+max(left,right)