判断二叉树是否为平衡二叉树

题目: 输入一颗二叉树的根节点,判断该树是不是平衡二叉树。

1.平衡二叉树

定义:一棵空树或它的任意节点的左右两个子树的高度差的绝对值均不超过1。

下面就是一颗平衡二叉树:

2.解法一

解题思路: 根据二叉树的定义,我们可以递归遍历二叉树的每一个节点来,求出每个节点的左右子树的高度,如果每个节点的左右子树的高度相差不超过1,按照定义,它就是一颗平衡二叉树。

参考如下代码:

//求二叉树的高度
int treeDepth(BinaryTreeNode* root){
    if(root==NULL){
        return 0;
    }
    int nLeft=treeDepth(root->m_pLeft);
    int nRight=treeDepth(root->m_pRight);
    return nLeft>nRight?nLeft+1:nRight+1;
}

bool isBalanced(BinaryTreeNode* root){
    if(root==NULL)
        return true;//空树是平衡二叉树
    int left= treeDepth(root->m_pLeft);
    int right= treeDepth(root->m_pRight);
    int diff=left-right;
    if(diff>1||diff<-1)
        return false;
    return isBalanced(root->m_pLeft)&&isBalanced(root->m_pRight);
}

优点:只要求出给定二叉树的高度,就可以方便的判断出二叉树是平衡二叉树,思路简单,代码简洁。

缺点:由于每个节点都会被重复遍历多次,这造成时间效率不高。例如在上面的函数输入isBalanced()函数中输入如下二叉树:

我们首先判断根节点1是不是平衡的,此时我们需要调用treeDepth()函数求根节点左子树的高度,需要遍历节点4、5、7。接下来需要判断以节点2为根节点的子树是不是平衡树的时候,分别求以节点2为根节点的左子树的高度和右子树的高度,这时又遍历了节点4、5、7。

很显然,节点的重复遍历会造成性能的下降,下面将给出每个节点只遍历一次的解法。

2.解法二

解题思路: 采用后序遍历的方式遍历二叉树的每一个节点,在遍历到一个节点之前我们就已经遍历了它的左右字数。此时,记录每个节点为根节点的树的高度,就可以一边遍历一边判断每个节点是不是平衡的。

参考代码:

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

    int nLeftDepth,nRightDepth;  
    bool bLeft= IsBalanced(pRoot->m_pLeft, &nLeftDepth);  
    bool bRight = IsBalanced(pRoot->m_pRight, &nRightDepth);  

    if (bLeft && bRight){  
        int diff = nRightDepth-nLeftDepth;  
        if (diff<=1 && diff>=-1) //左右字树高度差绝对值不超过1  
        {  
            *depth = 1+(nLeftDepth > nRightDepth ? nLeftDepth : nRightDepth);  
            return true;  
        }  
    }   
    return false;  
}  

bool IsBalanced(BinaryTreeNode* pRoot)  
{  
    int depth = 0;  

    return IsBalanced(pRoot, &depth);  
}  

参考文献

[1]http://blog.csdn.net/k346k346/article/details/51076268. [2]剑指Offer.何海涛.电子工业出版社.

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏撸码那些事

【图解数据结构】二叉查找树

12720
来自专栏编程坑太多

HashMap 源码解析

13420
来自专栏用户画像

4.3.2 线索二叉树

二叉树结点的各种遍历序列,其实质是对一个非线性结构进行线性化操作,使在这个访问序列中每一个结点(除第一个和最后一个)都有一个直接前驱和直接后继。

12120
来自专栏用户画像

4.3.1 二叉树的遍历

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

9520
来自专栏向治洪

数据结构之二叉树

二叉树的定义: 二叉树是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树的形式,即使是一般的树也能简单地转换为二叉树,而且二叉树的存储结构及...

22550
来自专栏java学习

让你更好的理解什么是二叉树?

二叉树 6.2.1 二叉树的概念 二叉树(Binary Tree)是结点的有限集合,这个集合或者为空,或者是由一个根结点和两颗互不相交的分别称为左子树和右子树的...

842110
来自专栏Bingo的深度学习杂货店

Q110 Balanced Binary Tree

Given a binary tree, determine if it is height-balanced. For this problem, a hei...

29450
来自专栏大闲人柴毛毛

剑指offer代码解析——面试题25二叉树中和为某一值的路径

题目:输入一棵二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。PS:从根结点开始,一直到叶子结点形式一条路径。 分析:要找出路径之和为指定整...

28550
来自专栏琯琯博客

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

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

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

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

19340

扫码关注云+社区

领取腾讯云代金券