判断二叉树是不是平衡

平衡二叉树(Balanced Binary Tree)又被称为AVL树(有别于AVL算法),且具有以下性质:它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。

题目:输入一棵二叉树的根结点,判断该树是不是平衡二叉树。如果某二叉树中任意结点的左右子树的深度相差不超过1,那么它就是一棵平衡二叉树。

例如下图中的二叉树就是一棵平衡二叉树:

本系列博客的第27题,我们曾介绍过如何求二叉树的深度。有了求二叉树的深度的经验之后再解决这个问题,我们很容易就能想到一个思路:在遍历树的每个结点的时候,调用函数TreeDepth得到它的左右子树的深度。如果每个结点的左右子树的深度相差都不超过1,按照定义它就是一棵平衡的二叉树

这种思路对应的代码如下:

int TreeDepth(SBinaryTreeNode *pTreeNode)
{
      if(!pTreeNode)
            return 0;
 
      int nLeft = TreeDepth(pTreeNode->m_pLeft);
      int nRight = TreeDepth(pTreeNode->m_pRight);
 
      return (nLeft > nRight) ? (nLeft + 1) : (nRight + 1);
}
bool IsBalanced(BinaryTreeNode* pRoot)
{
    if(pRoot == NULL)
        return true;

    int left = TreeDepth(pRoot->m_pLeft);
    int right = TreeDepth(pRoot->m_pRight);
    int diff = left - right;
    if(diff > 1 || diff < -1)
        return false;

    return IsBalanced(pRoot->m_pLeft) && IsBalanced(pRoot->m_pRight);
}

上面的代码固然简洁,但我们也要注意到由于一个节点会被重复遍历多次,这种思路的时间效率不高。例如在函数IsBalance中输入上图中的二叉树,首先判断根结点(值为1的结点)的左右子树是不是平衡结点。此时我们将往函数TreeDepth输入左子树根结点(值为2的结点),需要遍历结点4、5、7。接下来判断以值为2的结点为根结点的子树是不是平衡树的时候,仍然会遍历结点4、5、7。毫无疑问,重复遍历同一个结点会影响性能。接下来我们寻找不需要重复遍历的算法。

如果我们用后序遍历的方式遍历二叉树的每一个结点,在遍历到一个结点之前我们已经遍历了它的左右子树。只要在遍历每个结点的时候记录它的深度(某一结点的深度等于它到叶节点的路径的长度),我们就可以一边遍历一边判断每个结点是不是平衡的。

下面是这种思路的参考代码:

bool IsBalanced(BinaryTreeNode* pRoot, int* pDepth)
{
    if(pRoot == NULL)
    {
        *pDepth = 0;
        return true;
    }

    int left, right;
    if(IsBalanced(pRoot->m_pLeft, &left)
        && IsBalanced(pRoot->m_pRight, &right))
    {
        int diff = left - right;
        if(diff <= 1 && diff >= -1)
        {
            *pDepth = 1 + (left > right ? left : right);
            return true;
        }
    }

    return false;
}

我们只需要给上面的函数传入二叉树的根结点以及一个表示结点深度的整形变量就可以了:

bool IsBalanced(BinaryTreeNode* pRoot)
{
    int depth = 0;
    return IsBalanced(pRoot, &depth);
}

在上面的代码中,我们用后序遍历的方式遍历整棵二叉树。在遍历某结点的左右子结点之后,我们可以根据它的左右子结点的深度判断它是不是平衡的,并得到当前结点的深度。当最后遍历到树的根结点的时候,也就判断了整棵二叉树是不是平衡二叉树了。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏琯琯博客

PHP二叉树(一):平衡二叉树(AVL)

平衡二叉树 <?php /** * description: 平衡二叉树 */ //结点 class Node { public $key; ...

3359
来自专栏xingoo, 一个梦想做发明家的程序员

二叉排序树的删除操作

算法思想 二叉排序树,删除操作主要针对三种情况。 1 叶子节点-直接删除就可以了 2 没有左孩子的节点-直接嫁接右子树就可以了(没有右孩子的节点-直接嫁接左子树...

2358
来自专栏xcywt

《大话数据结构》树以及赫夫曼编码的例子

第六章 树 6.2 树的定义 树(Tree)的n个结点的有限集。当n=0时,称为空树。 任意一个非空树中: 1)有且仅有一个特定的称为根(root)的结点 2)...

4356
来自专栏章鱼的慢慢技术路

笔试常考题型之二叉树的遍历

1535
来自专栏撸码那些事

【图解数据结构】 树

1263
来自专栏大闲人柴毛毛

剑指offer代码解析——面试题19二叉树的镜像

   分析:所谓“镜像”就是从镜子里看到的样子。我们可以画一棵二叉树,然后画出该二叉树的镜像。画完图之后我们会发现,所谓“二叉树的镜像”就是把二叉树中所有子树...

2815
来自专栏用户画像

4.3.1 二叉树的遍历

所谓二叉树的遍历,是指按照某条搜索路径访问树中的每个结点,使得每个几点均被访问一次,而且仅被访问一次。

822
来自专栏武培轩的专栏

剑指Offer-按之字形顺序打印二叉树

package Tree; import java.util.ArrayList; import java.util.LinkedList; import j...

2754
来自专栏Android相关

平衡二叉树

它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。

3623
来自专栏weixuqin 的专栏

数据结构学习笔记(树、二叉树)

2603

扫码关注云+社区