求一棵树的高其实就是求树的层数。
节点存在,树高就是 1 。节点不存在认为是 0 或者 -1 。
思路
- 已知某个节点,并已知当前父节点树高。若节点不为空则树高 + 1 。
- 然后求其左子树的树高。
- 再去求其右子树的树高,取两者树高的最大值。
- 然后取当前节点树高和子树树高最大值的最大值。
上面的思路利用的是递归,同样可以转换成用栈实现,经过测试发现想要求树的高度,栈的实现方式貌似只能用后序遍历的形式。
- 在基于后序遍历的栈实现基础上,取当前栈的大小即为当前树高。
- 当遍历结束后,取最大值的栈大小即为最终的树高。
还有一种思路就是在创建二叉树的每个节点时,为其指定层级。以数组存储结构为例,根节点记为层级 1,那么其左节点和右节点都为 1 + 1,利用递归可以得到每个节点的层级属性。
这样一来,只要遍历二叉树找到最大的层级值就是当前二叉树的树高。
代码
github 地址:求一棵二叉树的高度
网友评论