从那个学年到现在已经有一段时间了。在一家医院找到了一份 IT 专家的工作。现在正在尝试进行一些实际的编程。我现在正在研究二叉树，我想知道确定树是否高度平衡的最佳方法是什么。
我在想一些事情：
public boolean isBalanced(Node root){
if(root==null){
return true; //tree is empty
}
else{
int lh = root.left.height();
int rh = root.right.height();
if(lh - rh > 1 || rh - lh > 1){
return false;
}
}
return true;
}
这是一个很好的实现吗？还是我错过了什么？
在寻找其他东西时偶然发现了这个老问题。我注意到您从未得到完整的答案。
解决此问题的方法是首先为您尝试编写的函数编写规范。
规范：如果（1）它是空的，或者（2）它的左右孩子高度平衡并且左树的高度在 1右树的高度。
既然您有了规范，那么编写代码就很简单了。只需遵循规范：
IsHeightBalanced(tree)
return (tree is empty) or
(IsHeightBalanced(tree.left) and
IsHeightBalanced(tree.right) and
abs(Height(tree.left) - Height(tree.right)) <= 1)
将其翻译成您选择的编程语言应该是微不足道的。
奖励练习：这个简单的代码草图在计算高度时遍历树的次数太多了。你能让它更有效率吗？
超级奖励练习：假设树严重不平衡。就像，一侧深一百万个节点，另一侧深三个。是否存在这种算法炸毁堆栈的情况？您能否修复实现以使其永远不会破坏堆栈，即使在给定大量不平衡树的情况下也是如此？
更新：Donal Fellows 在他的回答中指出，人们可以选择不同的“平衡”定义。例如，可以对“高度平衡”采取更严格的定义，并要求到最近的空孩子的路径长度在到最远的空孩子的路径之一内。我的定义没有那么严格，因此允许更多的树。
也可以没有我的定义那么严格；可以说，平衡树是这样一种树，其中每个分支上到一棵空树的最大路径长度相差不超过 2、3 或其他常数。或者最大路径长度是最小路径长度的一部分，例如一半或四分之一。
平时真的无所谓。任何树平衡算法的重点是确保您不会陷入一侧有一百万个节点而另一侧有三个节点的情况。Donal 的定义在理论上是好的，但在实践中，提出一种满足这种严格程度的树平衡算法是很痛苦的。性能节省通常不能证明实施成本是合理的。您花费大量时间进行不必要的树重新排列，以达到在实践中几乎没有什么区别的平衡水平。谁会在乎有时需要 40 个分支才能到达一棵百万节点的不完全平衡树中最远的叶子，而理论上它在完全平衡的树中只需要 20 个？关键是它永远不需要一百万。从一百万的最坏情况下降到四十的最坏情况通常就足够了。您不必一直寻找最佳情况。
平衡是一种真正微妙的属性。你以为你知道它是什么，但它很容易出错。特别是，即使是 Eric Lippert 的（好的）答案也是错误的。那是因为高度的概念是不够的。您需要了解树的最小和最大高度的概念（其中最小高度是从根到叶的最少步数，而最大高度是......好吧，你明白了）。鉴于此，我们可以将平衡定义为：
任何树枝的最大高度不超过任何树枝的最小高度的一棵树。
（这实际上意味着分支本身是平衡的；您可以选择相同的分支作为最大值和最小值。）
验证此属性所需要做的就是一个简单的树遍历来跟踪当前深度。第一次回溯时，会给你一个基线深度。之后每次回溯时，都会将新深度与基线进行比较
在代码中：
class Tree {
Tree left, right;
static interface Observer {
public void before();
public void after();
public boolean end();
}
static boolean traverse(Tree t, Observer o) {
if (t == null) {
return o.end();
} else {
o.before();
try {
if (traverse(left, o))
return traverse(right, o);
return false;
} finally {
o.after();
}
}
}
boolean balanced() {
final Integer[] heights = new Integer[2];
return traverse(this, new Observer() {
int h;
public void before() { h++; }
public void after() { h--; }
public boolean end() {
if (heights[0] == null) {
heights[0] = h;
} else if (Math.abs(heights[0] - h) > 1) {
return false;
} else if (heights[0] != h) {
if (heights[1] == null) {
heights[1] = h;
} else if (heights[1] != h) {
return false;
}
}
return true;
}
});
}
}
我想你可以在不使用观察者模式的情况下做到这一点，但我发现这样推理更容易。
[编辑]：为什么你不能只取每一边的高度。考虑这棵树：
/\
/ \
/ \
/ \_____
/\ / \_
/ \ / / \
/\ C /\ / \
/ \ / \ /\ /\
A B D E F G H J
好的，有点乱，但是根的每一边都是平衡的：C深度为 2，A，B，D，E深度为 3，F，G，H，J深度为 4。左分支的高度为 2（记住高度会随着您遍历而减小分支），右分支的高度为 3。但整个树并不平衡C，因为和之间的高度差为 2 F。您需要一个 minimax 规范（尽管实际算法可能不那么复杂，因为应该只有两个允许的高度）。
这仅确定树的顶层是否平衡。也就是说，你可以有一棵树，在最左边和最右边有两条长树枝，中间什么都没有，这将返回 true。在返回 true 之前，您需要递归检查root.leftandroot.right以查看它们是否也在内部平衡。
奖励练习反应。简单的解决方案。显然，在实际实现中，可能会包装这个或其他东西以避免要求用户在他们的响应中包含高度。
IsHeightBalanced(tree, out height)
if (tree is empty)
height = 0
return true
balance = IsHeightBalanced(tree.left, out heightleft) and IsHeightBalanced(tree.right, out heightright)
height = max(heightleft, heightright)+1
return balance and abs(heightleft - heightright) <= 1
发布订单解决方案，仅遍历树一次。时间复杂度为 O(n)，空间为 O(1)，比自顶向下的解决方案要好。我给你一个java版本的实现。
public static <T> boolean isBalanced(TreeNode<T> root){
return checkBalance(root) != -1;
}
private static <T> int checkBalance(TreeNode<T> node){
if(node == null) return 0;
int left = checkBalance(node.getLeft());
if(left == -1) return -1;
int right = checkBalance(node.getRight());
if(right == -1) return -1;
if(Math.abs(left - right) > 1){
return -1;
}else{
return 1 + Math.max(left, right);
}
}
高度平衡二叉树的定义是：
二叉树，其中每个节点的两个子树的高度相差不超过 1。
所以，一棵空的二叉树总是高度平衡的。
如果满足以下条件，则非空二叉树是高度平衡的：
考虑树：
A
\
B
/ \
C D
正如所见，它的左子树A是高度平衡的（因为它是空的），它的右子树也是如此。但是树仍然不是高度平衡的，因为条件 3 不满足，因为左子树的0高度是 并且右子树的高度是2。
即使左右子树的高度相等，下面的树也不是高度平衡的。您现有的代码将为它返回 true。
A
/ \
B C
/ \
D G
/ \
E H
所以def中的every这个词非常重要。
这将起作用：
int height(treeNodePtr root) {
return (!root) ? 0: 1 + MAX(height(root->left),height(root->right));
}
bool isHeightBalanced(treeNodePtr root) {
return (root == NULL) ||
(isHeightBalanced(root->left) &&
isHeightBalanced(root->right) &&
abs(height(root->left) - height(root->right)) <=1);
}
可以通过Level order traversal检查二叉树是否平衡：
private boolean isLeaf(TreeNode root) {
if (root.left == null && root.right == null)
return true;
return false;
}
private boolean isBalanced(TreeNode root) {
if (root == null)
return true;
Vector<TreeNode> queue = new Vector<TreeNode>();
int level = 1, minLevel = Integer.MAX_VALUE, maxLevel = Integer.MIN_VALUE;
queue.add(root);
while (!queue.isEmpty()) {
int elementCount = queue.size();
while (elementCount > 0) {
TreeNode node = queue.remove(0);
if (isLeaf(node)) {
if (minLevel > level)
minLevel = level;
if (maxLevel < level)
maxLevel = level;
} else {
if (node.left != null)
queue.add(node.left);
if (node.right != null)
queue.add(node.right);
}
elementCount--;
}
if (abs(maxLevel - minLevel) > 1) {
return false;
}
level++;
}
return true;
}
这比实际情况要复杂得多。
算法如下：
令 B = 最低层节点的深度
如果 abs(AB) <= 1，则树是平衡的
平衡意味着什么取决于手头的结构。例如，B-Tree 的节点不能超过距根的一定深度，或者更少，所有数据都位于距根的固定深度，但如果叶子到叶子的分布可能会失去平衡- 但一个节点是不均匀的。跳过列表完全没有平衡的概念，而是依靠概率来实现良好的性能。斐波那契树故意失去平衡，推迟重新平衡以实现卓越的渐近性能，以换取偶尔更长的更新。AVL 和红黑树将元数据附加到每个节点以获得深度平衡不变量。
所有这些结构以及更多结构都存在于大多数常见编程系统的标准库中（python、RAGE 除外！）。实现一两个是很好的编程实践，但它可能不是一个很好的利用时间来为生产滚动你自己的，除非你的问题有一些特殊的性能，不需要任何现成的集合来满足。
注 1：任何子树的高度只计算一次。
注 2：如果左子树不平衡，则跳过可能包含百万个元素的右子树的计算。
// return height of tree rooted at "tn" if, and only if, it is a balanced subtree
// else return -1
int maxHeight( TreeNode const * tn ) {
if( tn ) {
int const lh = maxHeight( tn->left );
if( lh == -1 ) return -1;
int const rh = maxHeight( tn->right );
if( rh == -1 ) return -1;
if( abs( lh - rh ) > 1 ) return -1;
return 1 + max( lh, rh );
}
return 0;
}
bool isBalanced( TreeNode const * root ) {
// Unless the maxHeight is -1, the subtree under "root" is balanced
return maxHeight( root ) != -1;
}
平衡通常取决于每个方向上最长路径的长度。上述算法不会为您做到这一点。
你想实现什么？周围有自平衡树（AVL/红黑）。事实上，Java 树是平衡的。
public boolean isBalanced(TreeNode root)
{
return (maxDepth(root) - minDepth(root) <= 1);
}
public int maxDepth(TreeNode root)
{
if (root == null) return 0;
return 1 + max(maxDepth(root.left), maxDepth(root.right));
}
public int minDepth (TreeNode root)
{
if (root == null) return 0;
return 1 + min(minDepth(root.left), minDepth(root.right));
}
这是一个完整的 C# 测试解决方案（对不起，我不是 java 开发人员）（只需在控制台应用程序中复制粘贴）。我知道平衡的定义各不相同，所以不是每个人都可能喜欢我的测试结果，但请看一下在递归循环中检查深度/高度并在第一次不匹配时退出而不在每个节点上保存节点高度/级别/深度的略有不同的方法（仅在函数调用中维护它）。
using System;
using System.Linq;
using System.Text;
namespace BalancedTree
{
class Program
{
public static void Main()
{
//Value Gathering
Console.WriteLine(RunTreeTests(new[] { 0 }));
Console.WriteLine(RunTreeTests(new int[] { }));
Console.WriteLine(RunTreeTests(new[] { 0, 1, 2, 3, 4, -1, -4, -3, -2 }));
Console.WriteLine(RunTreeTests(null));
Console.WriteLine(RunTreeTests(new[] { 10, 8, 12, 8, 4, 14, 8, 10 }));
Console.WriteLine(RunTreeTests(new int[] { 20, 10, 30, 5, 15, 25, 35, 3, 8, 12, 17, 22, 27, 32, 37 }));
Console.ReadKey();
}
static string RunTreeTests(int[] scores)
{
if (scores == null || scores.Count() == 0)
{
return null;
}
var tree = new BinarySearchTree();
foreach (var score in scores)
{
tree.InsertScore(score);
}
Console.WriteLine(tree.IsBalanced());
var sb = tree.GetBreadthWardsTraversedNodes();
return sb.ToString(0, sb.Length - 1);
}
}
public class Node
{
public int Value { get; set; }
public int Count { get; set; }
public Node RightChild { get; set; }
public Node LeftChild { get; set; }
public Node(int value)
{
Value = value;
Count = 1;
}
public override string ToString()
{
return Value + ":" + Count;
}
public bool IsLeafNode()
{
return LeftChild == null && RightChild == null;
}
public void AddValue(int value)
{
if (value == Value)
{
Count++;
}
else
{
if (value > Value)
{
if (RightChild == null)
{
RightChild = new Node(value);
}
else
{
RightChild.AddValue(value);
}
}
else
{
if (LeftChild == null)
{
LeftChild = new Node(value);
}
else
{
LeftChild.AddValue(value);
}
}
}
}
}
public class BinarySearchTree
{
public Node Root { get; set; }
public void InsertScore(int score)
{
if (Root == null)
{
Root = new Node(score);
}
else
{
Root.AddValue(score);
}
}
private static int _heightCheck;
public bool IsBalanced()
{
_heightCheck = 0;
var height = 0;
if (Root == null) return true;
var result = CheckHeight(Root, ref height);
height--;
return (result && height == 0);
}
private static bool CheckHeight(Node node, ref int height)
{
height++;
if (node.LeftChild == null)
{
if (node.RightChild != null) return false;
if (_heightCheck != 0) return _heightCheck == height;
_heightCheck = height;
return true;
}
if (node.RightChild == null)
{
return false;
}
var leftCheck = CheckHeight(node.LeftChild, ref height);
if (!leftCheck) return false;
height--;
var rightCheck = CheckHeight(node.RightChild, ref height);
if (!rightCheck) return false;
height--;
return true;
}
public StringBuilder GetBreadthWardsTraversedNodes()
{
if (Root == null) return null;
var traversQueue = new StringBuilder();
traversQueue.Append(Root + ",");
if (Root.IsLeafNode()) return traversQueue;
TraversBreadthWards(traversQueue, Root);
return traversQueue;
}
private static void TraversBreadthWards(StringBuilder sb, Node node)
{
if (node == null) return;
sb.Append(node.LeftChild + ",");
sb.Append(node.RightChild + ",");
if (node.LeftChild != null && !node.LeftChild.IsLeafNode())
{
TraversBreadthWards(sb, node.LeftChild);
}
if (node.RightChild != null && !node.RightChild.IsLeafNode())
{
TraversBreadthWards(sb, node.RightChild);
}
}
}
}
如果这是为了你的工作，我建议：
#include <iostream>
#include <deque>
#include <queue>
struct node
{
int data;
node *left;
node *right;
};
bool isBalanced(node *root)
{
if ( !root)
{
return true;
}
std::queue<node *> q1;
std::queue<int> q2;
int level = 0, last_level = -1, node_count = 0;
q1.push(root);
q2.push(level);
while ( !q1.empty() )
{
node *current = q1.front();
level = q2.front();
q1.pop();
q2.pop();
if ( level )
{
++node_count;
}
if ( current->left )
{
q1.push(current->left);
q2.push(level + 1);
}
if ( current->right )
{
q1.push(current->right);
q2.push(level + 1);
}
if ( level != last_level )
{
std::cout << "Check: " << (node_count ? node_count - 1 : 1) << ", Level: " << level << ", Old level: " << last_level << std::endl;
if ( level && (node_count - 1) != (1 << (level-1)) )
{
return false;
}
last_level = q2.front();
if ( level ) node_count = 1;
}
}
return true;
}
int main()
{
node tree[15];
tree[0].left = &tree[1];
tree[0].right = &tree[2];
tree[1].left = &tree[3];
tree[1].right = &tree[4];
tree[2].left = &tree[5];
tree[2].right = &tree[6];
tree[3].left = &tree[7];
tree[3].right = &tree[8];
tree[4].left = &tree[9]; // NULL;
tree[4].right = &tree[10]; // NULL;
tree[5].left = &tree[11]; // NULL;
tree[5].right = &tree[12]; // NULL;
tree[6].left = &tree[13];
tree[6].right = &tree[14];
tree[7].left = &tree[11];
tree[7].right = &tree[12];
tree[8].left = NULL;
tree[8].right = &tree[10];
tree[9].left = NULL;
tree[9].right = &tree[10];
tree[10].left = NULL;
tree[10].right= NULL;
tree[11].left = NULL;
tree[11].right= NULL;
tree[12].left = NULL;
tree[12].right= NULL;
tree[13].left = NULL;
tree[13].right= NULL;
tree[14].left = NULL;
tree[14].right= NULL;
std::cout << "Result: " << isBalanced(tree) << std::endl;
return 0;
}
回复：@lucky 的解决方案使用 BFS 进行级别顺序遍历。
我们遍历树并保留对 vars min/max-level 的引用，它描述了节点是叶子的最小级别。
我相信@lucky 解决方案需要修改。正如@codaddict 所建议的那样，我们必须检查左或右子节点是否为空（而不是两者），而不是检查节点是否为叶节点。否则，算法会认为这是一个有效的平衡树：
1
/ \
2 4
\ \
3 1
在 Python 中：
def is_bal(root):
if root is None:
return True
import queue
Q = queue.Queue()
Q.put(root)
level = 0
min_level, max_level = sys.maxsize, sys.minsize
while not Q.empty():
level_size = Q.qsize()
for i in range(level_size):
node = Q.get()
if not node.left or node.right:
min_level, max_level = min(min_level, level), max(max_level, level)
if node.left:
Q.put(node.left)
if node.right:
Q.put(node.right)
level += 1
if abs(max_level - min_level) > 1:
return False
return True
该解决方案应满足初始问题中提供的所有规定，在 O(n) 时间和 O(n) 空间中运行。内存溢出将被定向到堆而不是破坏递归调用堆栈。
或者，我们可以最初遍历树以迭代地计算 + 缓存每个根子树的最大高度。然后在另一个迭代运行中，检查每个根的左子树和右子树的缓存高度是否相差不超过一。这也将在 O(n) 时间和 O(n) 空间中运行，但要迭代运行，以免导致堆栈溢出。
好吧，你需要一种方法来确定左右的高度，以及左右是否平衡。
我只想return height(node->left) == height(node->right);
关于编写height函数，请阅读：
了解递归
你说的是什么树？那里有自平衡树。检查他们的算法，他们确定是否需要重新排序树以保持平衡。
这是一个基于通用深度优先遍历的版本。应该比其他正确答案更快并处理所有提到的“挑战”。为风格道歉，我真的不知道Java。
如果 max 和 min 都已设置并且差异 >1，您仍然可以通过提前返回来使其更快。
public boolean isBalanced( Node root ) {
int curDepth = 0, maxLeaf = 0, minLeaf = INT_MAX;
if ( root == null ) return true;
while ( root != null ) {
if ( root.left == null || root.right == null ) {
maxLeaf = max( maxLeaf, curDepth );
minLeaf = min( minLeaf, curDepth );
}
if ( root.left != null ) {
curDepth += 1;
root = root.left;
} else {
Node last = root;
while ( root != null
&& ( root.right == null || root.right == last ) ) {
curDepth -= 1;
last = root;
root = root.parent;
}
if ( root != null ) {
curDepth += 1;
root = root.right;
}
}
}
return ( maxLeaf - minLeaf <= 1 );
}
class Node {
int data;
Node left;
Node right;
// assign variable with constructor
public Node(int data) {
this.data = data;
}
}
public class BinaryTree {
Node root;
// get max depth
public static int maxDepth(Node node) {
if (node == null)
return 0;
return 1 + Math.max(maxDepth(node.left), maxDepth(node.right));
}
// get min depth
public static int minDepth(Node node) {
if (node == null)
return 0;
return 1 + Math.min(minDepth(node.left), minDepth(node.right));
}
// return max-min<=1 to check if tree balanced
public boolean isBalanced(Node node) {
if (Math.abs(maxDepth(node) - minDepth(node)) <= 1)
return true;
return false;
}
public static void main(String... strings) {
BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
if (tree.isBalanced(tree.root))
System.out.println("Tree is balanced");
else
System.out.println("Tree is not balanced");
}
}
Here's what i have tried for Eric's bonus exercise. I try to unwind of my recursive loops and return as soon as I find a subtree to be not balanced.
int heightBalanced(node *root){
int i = 1;
heightBalancedRecursive(root, &i);
return i;
}
int heightBalancedRecursive(node *root, int *i){
int lb = 0, rb = 0;
if(!root || ! *i) // if node is null or a subtree is not height balanced
return 0;
lb = heightBalancedRecursive(root -> left,i);
if (!*i) // subtree is not balanced. Skip traversing the tree anymore
return 0;
rb = heightBalancedRecursive(root -> right,i)
if (abs(lb - rb) > 1) // not balanced. Make i zero.
*i = 0;
return ( lb > rb ? lb +1 : rb + 1); // return the current height of the subtree
}
一棵空树是高度平衡的。如果满足以下条件，则非空二叉树 T 是平衡的：
1) T的左子树是平衡的
2）T的右子树是平衡的
3）左子树和右子树的高度差不大于1。
/* program to check if a tree is height-balanced or not */
#include<stdio.h>
#include<stdlib.h>
#define bool int
/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
};
/* The function returns true if root is balanced else false
The second parameter is to store the height of tree.
Initially, we need to pass a pointer to a location with value
as 0. We can also write a wrapper over this function */
bool isBalanced(struct node *root, int* height)
{
/* lh --> Height of left subtree
rh --> Height of right subtree */
int lh = 0, rh = 0;
/* l will be true if left subtree is balanced
and r will be true if right subtree is balanced */
int l = 0, r = 0;
if(root == NULL)
{
*height = 0;
return 1;
}
/* Get the heights of left and right subtrees in lh and rh
And store the returned values in l and r */
l = isBalanced(root->left, &lh);
r = isBalanced(root->right,&rh);
/* Height of current node is max of heights of left and
right subtrees plus 1*/
*height = (lh > rh? lh: rh) + 1;
/* If difference between heights of left and right
subtrees is more than 2 then this node is not balanced
so return 0 */
if((lh - rh >= 2) || (rh - lh >= 2))
return 0;
/* If this node is balanced and left and right subtrees
are balanced then return true */
else return l&&r;
}
/* UTILITY FUNCTIONS TO TEST isBalanced() FUNCTION */
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
int main()
{
int height = 0;
/* Constructed binary tree is
1
/ \
2 3
/ \ /
4 5 6
/
7
*/
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right->left = newNode(6);
root->left->left->left = newNode(7);
if(isBalanced(root, &height))
printf("Tree is balanced");
else
printf("Tree is not balanced");
getchar();
return 0;
}
时间复杂度：O(n)
public int height(Node node){
if(node==null)return 0;
else{
int l=height(node.leftChild);
int r=height(node.rightChild);
return(l>r?l+1:r+1);
}}
public boolean balanced(Node n){
int l= height(n.leftChild);
int r= height(n.rightChild);
System.out.println(l + " " +r);
if(Math.abs(l-r)>1)
return false;
else
return true;
}
为了在大树上获得更好的性能，您可以保存每个节点的高度，因此这是空间与性能的权衡：
class Node {
Node left;
Node right;
int value;
int height;
}
实现增删减的例子
void addNode(Node root,int v)
{ int height =0;
while(root != null)
{
// Since we are adding new node so the height
// will increase by one in each node we will pass by
root.height += 1;
height++;
else if(v > root.value){
root = root.left();
}
else{
root = root.right();
}
}
height++;
Node n = new Node(v , height);
root = n;
}
int treeMaxHeight(Node root)
{
return Math.Max(root.left.height,root.right.height);
}
int treeMinHeight(Node root)
{
return Math.Min(root.left.height,root.right.height);
}
Boolean isNodeBlanced(Node root)
{
if (treeMaxHeight(root) - treeMinHeight(root) > 2)
return false;
return true;
}
Boolean isTreeBlanced (Node root)
{
if(root == null || isTreeBalanced(root.left) && isTreeBalanced(root.right) && isNodeBlanced(root))
return true;
return false;
}
递归检查每个子树是否平衡。递归意味着，您向子树请求某些内容，子树将返回响应。你一直在问，直到你达到基本情况。在树问题中，基本情况是当您点击叶节点时。
在这种情况下，我们向子树提出 2 个问题：
1-你平衡吗？
2-你的身高是多少？
所以递归函数将返回 2 个答案，我将这些答案保存在数组中。
这是python代码：
class Solution:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
def dfs(root):
# leaf node is balanced
if not root:
# we carry the height of each subtree
return [True,0]
# with recursion, we start from bottom, so we do not have repetitive work
left,right=dfs(root.left),dfs(root.right)
# if any of the subtree return false, then we know entire tree is not balanced
balanced=left[0] and right[0] and abs(left[1]-right[1])<=1
# 1+max(left[1],right[1]) is the height of the each subtree. 1 is the root of the subtree
return [balanced,1+max(left[1],right[1])]
return dfs(root)[0]
这是javascript代码：
var isBalanced = function(root) {
function dfs(root){
if(!root){
return [true,0]
}
const left=dfs(root.left)
const right=dfs(root.right)
const balanced=left[0] && right[0] && Math.abs(left[1]-right[1])<=1
return [balanced,1+Math.max(left[1],right[1])]
}
return dfs(root)[0]
};
static boolean isBalanced(Node root) {
//check in the depth of left and right subtree
int diff = depth(root.getLeft()) - depth(root.getRight());
if (diff < 0) {
diff = diff * -1;
}
if (diff > 1) {
return false;
}
//go to child nodes
else {
if (root.getLeft() == null && root.getRight() == null) {
return true;
} else if (root.getLeft() == null) {
if (depth(root.getRight()) > 1) {
return false;
} else {
return true;
}
} else if (root.getRight() == null) {
if (depth(root.getLeft()) > 1) {
return false;
} else {
return true;
}
} else if (root.getLeft() != null && root.getRight() != null && isBalanced(root.getLeft()) && isBalanced(root.getRight())) {
return true;
} else {
return false;
}
}
}
这不行吗？
return ( ( Math.abs( size( root.left ) - size( root.right ) ) < 2 );
任何不平衡的树都会失败。