歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

平衡二叉樹(二叉樹深度+DFS)

題目描述

輸入一棵二叉樹,判斷該二叉樹是否是平衡二叉樹。

平衡二叉樹:又稱AVL樹,

具有如下性質:

它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過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 pRoot is None:
         return True

        def DFS(root):

         # 如果說當前結點為None,返回0
         if not root:
          return 0
         # 返回左子樹和右子樹的最大值加1
         return max(DFS(root.right), DFS(root.left)) + 1

        h1 = DFS(pRoot.right)
        h2 = DFS(pRoot.left)
        # 如果說不滿足平衡二叉樹的性質,返回False
        if abs(h1 - h2) > 1:
         return False
        # 繼續判斷左子樹和右子樹是否滿足二叉樹的性質
        return self.IsBalanced_Solution(pRoot.right) and self.IsBalanced_Solution(pRoot.left)

求二叉樹中兩個節點的最遠距離 http://www.linuxidc.com/Linux/2016-08/134049.htm

根據二叉樹的前序數組和中序序遍歷數組生成二叉樹 http://www.linuxidc.com/Linux/2016-09/135514.htm

判斷一個二叉樹是否是平衡二叉樹 http://www.linuxidc.com/Linux/2016-07/132842.htm

輕松搞定面試中的二叉樹題目 http://www.linuxidc.com/linux/2014-07/104857.htm

二叉樹的先序、中序、後序遍歷 http://www.linuxidc.com/Linux/2016-06/132504.htm

Copyright © Linux教程網 All Rights Reserved