原题&翻译

Given a binary tree, determine if it is height-balanced.

给出二叉树,确定是否平高度平衡。

For this problem, a height-balanced binary tree is defined as:

平衡二叉树定义如下

一颗二叉树任意两个左右子树高度差绝对值不能大于 1.
二叉树

例子 1 :

给出如下二叉树 [3,9,20,null,null,15,7]:

返回 true

给出如下二叉树 [1,2,2,3,3,null,null,4,4]:

返回 false


基本思路

解法一

基本思想,每一个左右子树都判断深度。这导致每个节点多次计算,效率低下。

解法二

在 leetcode 上发现的又比较好理解的方式,asbear 的方法,很巧妙。从最深处开始判断左右子树深度是否接近,并将深度值向上传递,减少重复判断时间。只遍历一遍。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

相关文章

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部