美文网首页
二叉树计算高度

二叉树计算高度

作者: 王小宝wy | 来源:发表于2017-03-18 22:05 被阅读0次

最近自己犯了一个愚蠢至极的错误,被问到如何计算一颗平衡二叉树的高度,居然一时没想起来,其实答案相当简单,用句老师们经常爱讲的话就是,这是道送分题啊,结果自己居然没把握住...(真恨不得弄死自己)

言归正传,如果知道一棵平衡树的元素数目m,则二叉树的高度为log2m,由此可写出代码

public class BinaryTreeNode<T> {
    public T element;

    public BinaryTreeNode<T> left, right;

    public BinaryTreeNode(T element) {
        this.element = element;
        this.left = null;
        this.right = null;
    }

    public int numChildren() {
        int childrenCount = 0;
        if (left != null) {
            childrenCount = 1 + left.numChildren();
        }

        if (right != null) {
            childrenCount = childrenCount + 1 + right.numChildren();
        }

        return childrenCount;
    }

    public int getHeight(int nodesNum) {
        return (int)(Math.log(nodesNum) / Math.log(2));
    }
}

相关文章

  • 运用

    递归应用,计算二叉树的深度和二叉树的高度。自顶向下和自顶向上的思路

  • 二叉树相关的知识点

    关于二叉树高度的计算,通过递归的方式得到,跳出递归的条件是,当结点是None的时候,高度为0

  • 数据结构与算法之二叉树遍历(七)

    目录 前序遍历中序遍历后序遍历层序遍历遍历方式的选择条件根据遍历结果重构二叉树翻转二叉树计算二叉树的高度判断一棵树...

  • 数据结构之二叉树

    数据结构之二叉树 本文讲解二叉树的基本操作: 查找节点 计算树的高度 清空树 递归遍历:先序遍历、中序遍历、后序遍...

  • 剑指 Offer 55 - II. 平衡二叉树

    解题思路 首先明白平衡二叉树的树的高度是如何计算的Math.max(l,r)+1//左子树和右子树的最大高度+1通...

  • 2021-06-26二叉树

    分类 树、二叉树二叉查找树平衡二叉树、红黑树递归树 重点 计算公式 节点高度 = 节点到叶子节点的最长路径(边数)...

  • 2021-11-06 110. 平衡二叉树【Easy】

    给定一个二叉树,判断它是否是高度平衡的二叉树。一棵高度平衡二叉树定义为:一个二叉树每个节点 的左右两个子树的高度差...

  • 二叉树计算高度

    最近自己犯了一个愚蠢至极的错误,被问到如何计算一颗平衡二叉树的高度,居然一时没想起来,其实答案相当简单,用句老师们...

  • [leetcode] 二叉树最大高度

    示例:设计算法求给定二叉树的最大告诉,如下图二叉树返回的最大高度是3 最容易想到的是可以类似树的层序遍历,我们可以...

  • Leetcode 110 平衡二叉树

    平衡二叉树 题目 给定一个二叉树,判断它是否是高度平衡的二叉树。 本题中,一棵高度平衡二叉树定义为: 一个二叉树每...

网友评论

      本文标题:二叉树计算高度

      本文链接:https://www.haomeiwen.com/subject/gkmpnttx.html