美文网首页
算法-求一棵二叉树的高度

算法-求一棵二叉树的高度

作者: jkwen | 来源:发表于2021-05-16 12:52 被阅读0次

求一棵树的高其实就是求树的层数。

节点存在,树高就是 1 。节点不存在认为是 0 或者 -1 。

思路

  1. 已知某个节点,并已知当前父节点树高。若节点不为空则树高 + 1 。
  2. 然后求其左子树的树高。
  3. 再去求其右子树的树高,取两者树高的最大值。
  4. 然后取当前节点树高和子树树高最大值的最大值。

上面的思路利用的是递归,同样可以转换成用栈实现,经过测试发现想要求树的高度,栈的实现方式貌似只能用后序遍历的形式。

  1. 在基于后序遍历的栈实现基础上,取当前栈的大小即为当前树高。
  2. 当遍历结束后,取最大值的栈大小即为最终的树高。

还有一种思路就是在创建二叉树的每个节点时,为其指定层级。以数组存储结构为例,根节点记为层级 1,那么其左节点和右节点都为 1 + 1,利用递归可以得到每个节点的层级属性。

这样一来,只要遍历二叉树找到最大的层级值就是当前二叉树的树高。

代码

github 地址:求一棵二叉树的高度

相关文章

  • 判断一个树是否是BST 求一棵平衡二叉树的最小深度 判断一棵二叉树是否高度平衡

  • 2. 求二叉树的高度

    题目 定义一个方法,实现输入一棵二叉树,输出这棵二叉树的高度。 解题之法 本篇博客内容转载自[《求二叉树的高度(后...

  • 算法-求一棵二叉树的高度

    求一棵树的高其实就是求树的层数。 节点存在,树高就是 1 。节点不存在认为是 0 或者 -1 。 思路 已知某个节...

  • 平衡二叉树

    描述 给定一个二叉树, 确定它是高度平衡的。对于这个问题, 一棵高度平衡的二叉树的定义是:一棵二叉树中每个节点的两...

  • 二叉树遍历应用

    【例】输出二叉树中的叶子节点 【例】求二叉树高度

  • LintCode 93. 平衡二叉树

    题目描述 给定一个二叉树,确定它是高度平衡的。对于这个问题,一棵高度平衡的二叉树的定义是:一棵二叉树中每个节点的两...

  • [leetcode] 二叉树最大高度

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

  • OJ:lintcode 平衡二叉树

    给定一个二叉树,确定它是高度平衡的。对于这个问题,一棵高度平衡的二叉树的定义是:一棵二叉树中每个节点的两个子树的深...

  • 小米-基础算法-判断平衡二叉树

    给定一个二叉树,确定它是高度平衡的。对于这个问题,一棵高度平衡的二叉树的定义是:一棵二叉树中每个节点的两个子树的深...

  • 平衡二叉树

    LeetCode题目地址 给定一个二叉树,确定它是高度平衡的。对于这个问题,一棵高度平衡的二叉树的定义是:一棵二叉...

网友评论

      本文标题:算法-求一棵二叉树的高度

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