龙空技术网

483,完全二叉树的节点个数

数据结构和算法 139

前言:

此时你们对“计算二叉树高度”大约比较讲究,朋友们都想要剖析一些“计算二叉树高度”的相关资讯。那么小编在网上收集了一些对于“计算二叉树高度””的相关资讯,希望小伙伴们能喜欢,看官们一起来了解一下吧!

想了解更多数据结构以及算法题,可以关注微信公众号“数据结构和算法”,每天一题为你精彩解答。

问题描述

给出一个完全二叉树,求出该树的节点个数。

说明:

完全二叉树的定义如下:在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层,则该层包含 1~ 2^h 个节点。

示例:

输入:     1   / \  2   3 / \  /4  5 6输出: 6

1,DFS解决

这题是让求完全二叉树的节点个数,最简单的一种方式就是使用DFS,也就是递归解决。如果当前节点为空,直接返回0即可,否则就返回左子节点的个数+右子节点的个数+1。原理比较简单,直接一行代码搞定

public void levelOrder(TreeNode tree) {    if (tree == null)        return;    Queue<TreeNode> queue = new LinkedList<>();    queue.add(tree);    while (!queue.isEmpty()) {        //poll方法相当于移除队列头部的元素        TreeNode node = queue.poll();        System.out.println(node.val);        //如果左子节点不为空就把他加入到队列中        if (node.left != null)            queue.add(node.left);        //如果右子节点不为空也把他加入到队列中        if (node.right != null)            queue.add(node.right);    }}

2,BFS解决

之前讲过二叉树的几种遍历方式373,数据结构-6,树,有前序遍历,中序遍历,后序遍历,BFS,DFS,每种写法都包含递归和非递归,我们只需要把所有的节点都遍历一遍就可以统计出来了,如果每个都写一遍,有点多了,这里就使用BFS来写一个,二叉树的BFS代码如下。

public void levelOrder(TreeNode tree) {    if (tree == null)        return;    Queue<TreeNode> queue = new LinkedList<>();    queue.add(tree);    while (!queue.isEmpty()) {        //poll方法相当于移除队列头部的元素        TreeNode node = queue.poll();        System.out.println(node.val);        //如果左子节点不为空就把他加入到队列中        if (node.left != null)            queue.add(node.left);        //如果右子节点不为空也把他加入到队列中        if (node.right != null)            queue.add(node.right);    }}

我们来对它进行改造一下,统计节点的个数

public int countNodes(TreeNode root) {    if (root == null)        return 0;    int count = 0;    Queue<TreeNode> queue = new LinkedList<>();    queue.add(root);    while (!queue.isEmpty()) {        //poll方法相当于移除队列头部的元素        TreeNode node = queue.poll();        count++;//统计节点的个数        if (node.left != null)            queue.add(node.left);        if (node.right != null)            queue.add(node.right);    }    return count;}

3,从左子树找树的高度

题中对完全二叉树的描述已经很清晰了,如果我们还是用上面的两种方式一个个遍历的话,效果明显不是很好,可以考虑下面这种方式

先计算树的高度height,然后计算右子树的高度

1,如果右子树的高度等于height-1,说明左子树是满二叉树(如下图所示),可以通过公式(2^(height-1))-1计算即可,不需要全部遍历,然后再通过递归的方式计算右子树……,

2,如果右子树的高度不等于height-1,说明右子树是满二叉树(如下图所示),只不过比上面那种少了一层,也就是height-2,也可以通过公式(2^(height-2))-1计算,然后再通过递归的方式计算左子树……,

搞懂了上面的原理,代码就简单多了

public int countNodes(TreeNode root) {    //计算树的高度,    int height = treeHeight(root);    //如果树是空的,或者高度是1,直接返回    if (height == 0 || height == 1)        return height;    //如果右子树的高度是树的高度减1,说明左子树是满二叉树,    //左子树可以通过公式计算,只需要递归右子树就行了    if (treeHeight(root.right) == height - 1) {        //注意这里的计算,左子树的数量是实际上是(1 << (height - 1))-1,        //不要把根节点给忘了,在加上1就是(1 << (height - 1))        return (1 << (height - 1)) + countNodes(root.right);    } else {        //如果右子树的高度不是树的高度减1,说明右子树是满二叉树,可以通过        //公式计算右子树,只需要递归左子树就行了        return (1 << (height - 2)) + countNodes(root.left);    }}//计算树的高度private int treeHeight(TreeNode root) {    return root == null ? 0 : 1 + treeHeight(root.left);}

或者我们还可以把它改为非递归的

public int countNodes(TreeNode root) {    int count = 0, height = treeHeight(root);    while (root != null) {        //如果右子树的高度是树的高度减1,那么左子树就是满二叉树        if (treeHeight(root.right) == height - 1) {//左子树是满二叉树            count += 1 << height - 1;            root = root.right;        } else {//右子树是满二叉树            count += 1 << height - 2;            root = root.left;        }        height--;    }    return count;}//计算树的高度private int treeHeight(TreeNode root) {    return root == null ? 0 : 1 + treeHeight(root.left);

4,从右子树找树的高度

上面是先计算二叉树的高度,它是从左子节点一直往下走,找到树的高度。还可以换种思路从树的右子节点往下走,找到树的高度,原理都差不多,代码中有详细注释,就不在过多介绍

public int countNodes(TreeNode root) {    if (root == null)        return 0;    //计算高度,注意这里不是树的实际高度    int height = treeHeight(root);    if (treeHeight(root.left) == height) {//左子树是满二叉树,通过公式计算        return (1 << height) + countNodes(root.right);    } else {//右子树是满二叉树,通过公式计算        return (1 << height - 1) + countNodes(root.left);    }}//计算树的高度,注意这个结果不是树的实际高度,如果树是满二叉树,他就是树的//高度,如果不是满二叉树,他就是树的高度减1private int treeHeight(TreeNode root) {    return root == null ? 0 : 1 + treeHeight(root.right);//注意这里遍历的是树的右结点

5,总结

二叉树的遍历方式除了之前讲373,数据结构-6,树中的前序,中序,后续,以及BFS以外,还有莫里斯的前中后3种遍历方式。这些遍历方式有的还包含递归以及非递归等多种写法,如果都写一遍的话答案就非常多了。但这里说的是完全二叉树,我们可以根据完全二叉树的特性来计算,没必要把所有的节点都要遍历一遍。

二叉树常见的几种遍历方式(包括前序,中序,后序,DFS,BFS)在第373题都有过介绍,并且都有递归和非递归等多种实现方式。关于二叉树的莫里斯(Morris)的3种遍历方式后面有时间也会做介绍,期待大家一块学习。

标签: #计算二叉树高度