二叉树-039-平衡二叉树

题目描述

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

分析

1. 方法一： 根据以求得的二叉树的深度解，来构建此题的解是非常容易的。

   1. 存在问题重复遍历，时间复杂度是爆炸性的。

2. 后序一次遍历，判断该树节点是不是平衡的，知道遍历完。

代码

1. 法一（不推荐）：

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def TreeDepth(self, pRoot):
        # write code here
        if not pRoot:
            return 0
        
        nLeft = self.TreeDepth(pRoot.left)
        nRight = self.TreeDepth(pRoot.right)
        
        return max(nLeft+1,nRight+1)
    
    def IsBalanced_Solution(self, pRoot):
        # write code here
        if not pRoot:
            return True
        
        nLeft = self.TreeDepth(pRoot.left)
        nRight = self.TreeDepth(pRoot.right)
        
        diff = nLeft-nRight
        if diff < -1 or diff > 1:
            return False
        
        return self.IsBalanced_Solution(pRoot.left) and self.IsBalanced_Solution(pRoot.right)

2. 法二（推荐）：

# -*- 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
        return self.IsBalance(pRoot) != -1
     
    def IsBalance(self,pRoot):
        if not pRoot:
            return 0
         
        nLeft = self.IsBalance(pRoot.left)  #左子树不平衡返回-1，否则返回左子树深度
        if nLeft == -1:
            return -1
        nRight = self.IsBalance(pRoot.right) #右子树不平衡返回-1，否则返回右子树深度
        if nRight == -1:
            return -1
         
        diff = nLeft - nRight   # 如果左右子树深度差绝对值>1,则返回-1。
        if diff > 1 or diff < -1:
            return -1
         
        return max(nLeft,nRight)+1   # 没返回-1，则返回树深度。