求二叉树的深度和宽度

1 二叉树的深度

题目: 输入一个二叉树的根节点,求该树的深度。从根节点到叶子节点依次经过的节点(含根、叶节点)形成树的一条路径,最长路径的长度包含的节点数为为树的深度,即二叉树节点的层数。

二叉树的节点定义: 假定二叉树的节点定义如下:

struct BinaryTreeNode{
    int m_value;
    BinaryTreeNode* m_pLeft;
    BinaryTreeNode* m_pRight;
};

二叉树示例: 以图深度为四的二叉树为例,其先先根遍历序列为:{1,2,4,5,7,3,6},中根遍历序列为:{4,2,7,5,1,3,6},根据先根序列和中根序列即可构造唯一的二叉树,构造的具体实现可参见:二叉树的构造与遍历。很显然,该二叉树有4层节点,所以其高度是4。

求解思路: 根据题目的定义,我们可以用先根次序来遍历二叉树中所有根节点到叶节点的路径,来得到最长的路径就是二叉树的高度。但是这样的代码量较为冗长,我们可以采用递归的方式解决。

我们可以从根节点即左右子树来理解二叉树的深度。对于任意一棵非空二叉树,有如下四种情况:

(1)如果一颗树只有一个节点,它的深度是1;

(2)如果根节点只有左子树而没有右子树,那么二叉树的深度应该是其左子树的深度加1;

(3)如果根节点只有右子树而没有左子树,那么二叉树的深度应该是其右树的深度加1;

(4)如果根节点既有左子树又有右子树,那么二叉树的深度应该是其左右子树的深度较大值加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;
}

2 二叉树的宽度

题目: 给定一颗二叉树,求二叉树的宽度。

宽度的定义: 二叉树的宽度定义为具有最多结点数的层中包含的结点数。

比如上图中,第1层有1个节点, 第2层有2个节点, 第3层有4个节点, 第4层有1个节点,可知,第3层的结点数最多,所以这棵二叉树的宽度就是4。

求解思路: 这里需要用到二叉树的层次遍历,即广度优先周游。在层次遍历的过程中,通过读取队列中保留的上一层的节点数来记录每层的节点数,以获取所有层中最大的节点数。关于二叉树的广度优先周游,参考:二叉树的构造与遍历

具体实现:

//求二叉树的宽度  
int treeWidth(BinaryTreeNode *pRoot){  
    if (pRoot == NULL)
        return 0;  

    int nLastLevelWidth = 0;//记录上一层的宽度  
    int nCurLevelWidth = 0;//记录当前层的宽度  

    queue<BinaryTreeNode*> myQueue;  
    myQueue.push(pRoot);//将根节点入队列  
    int nWidth = 1;//二叉树的宽度  
    nLastLevelWidth = 1;      
    BinaryTreeNode *pCur = NULL;  

    while (!myQueue.empty())//队列不空  
    {  
        while (nLastLevelWidth!= 0){  
            pCur = myQueue.front();//取出队列头元素  
            myQueue.pop();//将队列头元素出对  

            if (pCur->m_pLeft != NULL)  
                myQueue.push(pCur->m_pLeft);   

            if (pCur->m_pRight != NULL)  
                myQueue.push(pCur->m_pRight); 
            nLastLevelWidth--;  
        }  

        nCurLevelWidth = myQueue.size();  
        nWidth = nCurLevelWidth > nWidth ? nCurLevelWidth : nWidth;  
        nLastLevelWidth = nCurLevelWidth;  
    }  
    return nWidth;  
}  

参考文献

[1]剑指Offer.何海涛.电子工业出版社. [2]求二叉树的深度和宽度

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏青玉伏案

算法与数据结构(十一) 平衡二叉树(AVL树)(Swift版)

今天的博客是在上一篇博客的基础上进行的延伸。上一篇博客我们主要聊了二叉排序树,详情请戳《二叉排序树的查找、插入与删除》。本篇博客我们就在二叉排序树的基础上来聊聊...

26370
来自专栏从流域到海域

校招必考:根据二叉树遍历序列确定二叉树

根据二叉树的前序遍历和中序遍历求其后序遍历或者根据二叉树的后序遍历和中序遍历求其前序遍历是腾讯等校招的必考题,下面我们就来分析一下解题思路。 这道题本质上...

23950
来自专栏向治洪

数据结构之二叉树

树 定义:满足以下条件的就是树: 1. 有且仅有一个特定的称为根Root的结点。 2. 当n>1时,其余结点可分为m(m>0)个互不相交的有限集,其...

214100
来自专栏java学习

请你对Java中树的了解有多少?

树 1200101班的学生信息表如图6.1所示,其中学生被分到了不同的学习小组,第一组组长是李华,组员有王丽、张阳、赵斌; 第二组组长是孙琪,组员有马丹; 第三...

39350
来自专栏灯塔大数据

每周学点大数据 | No.24二叉搜索树回顾(一)

No.24期 二叉搜索树回顾(一) Mr. 王:接下来我们谈一谈外存查找结构。内存中的查找结构最典型的就是二查搜索树了。这里我们先来简单地认识一下关于二叉树...

36350
来自专栏向治洪

ArrayList和LinkedList的区别

一般大家都知道ArrayList和LinkedList的大致区别: 1.ArrayList是实现了基于动态数组的数据结构,LinkedList基于链表的数据结构...

20990
来自专栏编程理解

数据结构(一):二叉树

二叉树( binary tree )是有限节点集合构成的结构,其结构的递归定义为:

14520
来自专栏程序生活

二叉树的深度

题目描述 输入一棵二叉树,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。 代码实现 递归实现 # ...

27240
来自专栏武培轩的专栏

Leetcode#104. Maximum Depth of Binary Tree(二叉树的最大深度)

15220
来自专栏kevindroid

leetcode110 Balanced Binary Tree

15750

扫码关注云+社区

领取腾讯云代金券