Skip to content

Latest commit

 

History

History
 
 

109. Balanced Binary Tree

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 
 
 

这道题,我昨天就在想了。毕竟平衡搜索树只不过是特殊的平衡二叉树罢了。是否平衡的关键在于题目里给出的这个定义:

a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

所以这个问题很重要的一个子问题就是:如何求二叉树的高度。假设我们找到了高度的方法,那么核心判断就是:

std::abs(height(root->left), height(root->right)) <= 1

所以我几乎是瞬间写出了解决方法(递归真的是人类自然而然的思路呀)。 但往往自然的思路,有时会伴随着效率低下,虽然被 LeetCode 认可了的(可AC)。


于是我尝试缩减递归次数,能想到的办法就是及早的判断出非平衡,然后跳出递归。那么又回到上面的判断核心上,只要那个条件不成立,我就应该跳出递归。可是如何能跳出递归呢?

我能想到的方法就是设一个 bool 成员变量,然后一旦为 false, 立刻停止。这就是目前我的方案了。

希望抛砖引玉,了解更多的方案。


最近持续不断的做有关 tree 的题目,让我深深感觉到,在树算法中,不用递归简直是找死,自建栈也好,自建队列也好, 都要维护一大堆东西,在效率上不仅没有显著的提升,反而让程序晦涩难懂,表意不明。如何抉择呢?我一定还是偏向于使用递归的。

在效率没有明显提升的情况下,递归表达意图的能力,实在是让人无法割舍。