剑指Offer(三十九):平衡二叉树

  • A+
所属分类:剑指Offer
摘要

输入一棵二叉树,判断该二叉树是否是平衡二叉树。

剑指Offer(三十九):平衡二叉树

一、前言

本系列文章为《剑指Offer》刷题笔记。

刷题平台:牛客网

书籍下载:共享资源

二、题目

输入一棵二叉树,判断该二叉树是否是平衡二叉树

1、思路

平衡二叉树的定义是:所谓的平衡之意,就是树中任意一个结点下左右两个子树的高度差不超过 1。

解题思路有两种,只遍历一次的方法最优。

重复遍历多次:

在遍历树的每个结点的时候,调用函数TreeDepth得到它的左右子树的深度。如果每个结点的左右子树的深度相差都不超过1,则这是一颗平衡的二叉树。这种方法的缺点是,首先判断根结点是不是平衡的,需要使用TreeDepth获得左右子树的深度,然后还需要继续判断子树是不是平衡的,还是需要使用TreeDepth获得子树的左右子树的深度,这样就导致了大量的重复遍历。

只遍历一次:

重复遍历会影响算法的性能,所以很有必要掌握不需要重复遍历的方法。如果我们用后序遍历的方式遍历二叉树的每一个结点,在遍历到一个结点之前我们就已经遍历了它的左右子树。只要在遍历每个结点的时候记录它的深度(某一结点的深度等于它到叶结点的路径的长度),我们就可以一边遍历一边判断每个结点是不是平衡的。

2、代码

C++:

重复遍历多次:

只遍历一次:

Jack Cui

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: