如何确定二叉树是否平衡？

小开

这只能确定树的顶层是否是平衡的。也就是说，你可以有一棵树，在最左边和最右边有两根长长的树枝，中间什么也没有，这将返回真。在返回 true 之前，需要递归地检查 root.left和 root.right，看看它们是否也是内部平衡的。

小开

你需要一种方法来确定左和右的高度，如果左和右是平衡的。

And I'd just return height(node->left) == height(node->right);

As to writing a height function, read: 理解递归

小开

你说的是哪种树？外面有自我平衡树。检查他们的算法，确定是否需要重新排序树以保持平衡。

小开

平衡通常取决于每个方向上最长路径的长度。上面的算法不会为您做到这一点。

您试图实现什么? 周围有自平衡树(AVL/Red-black)。事实上，Java 树是平衡的。

小开

如果这是你的 job，我建议:

do not reinvent the wheel and
使用/购买 COTS 代替摆弄比特。
为解决业务问题节省时间/精力。

小开

平衡意味着什么，有点取决于手头的结构。例如，B-Tree 的节点不能超过根的一定深度，或者更少，因为所有数据都存在于根的一个固定深度，但是如果叶子到叶子的分布不均衡，它就会失去平衡。跳过列表完全没有平衡的概念，而是依靠概率来实现良好的性能。斐波那契树故意失去平衡，延迟重新平衡以获得更好的渐近性能，以换取偶尔更长的更新。AVL 和 Red-Black 树将元数据附加到每个节点以获得深度平衡不变量。

所有这些结构以及更多的结构都存在于大多数常见编程系统的标准库中(除了 python、 RAGE!).实现一个或两个是很好的编程实践，但是它可能不能很好地利用您自己的时间进行生产，除非您的问题有一些特殊的性能需求，而任何现成的集合都无法满足这些性能需求。

小开

Wouldn't this work?

return ( ( Math.abs( size( root.left ) - size( root.right ) ) < 2 );

任何不平衡的树都会失败。

小开

在寻找其他东西的时候偶然发现了这个古老的问题。我注意到你从来没有得到一个完整的答案。

解决这个问题的方法是首先为您正在尝试编写的函数编写一个规范。

Specification: A well-formed binary tree is said to be "height-balanced" if (1) it is empty, or (2) its left and right children are height-balanced and the height of the left tree is within 1 of the height of the right tree.

Now that you have the specification, the code is trivial to write. Just follow the specification:

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 在他的回答中指出，人们可以选择不同的“平衡”定义。例如，可以对“高度平衡”进行更严格的定义，并要求到 最近的空子节点的路径长度位于到 最远的地方空子节点的路径之一内。我的定义没有那么严格，因此允许更多的树。

也可以不像我的定义那么严格; 可以说，平衡树是每个分支上空树的最大路径长度相差不超过两个或三个或其他常数的树。或者最大路径长度是最小路径长度的一部分，比如半个或四分之一个。

一般来说没什么大不了的。任何树平衡算法的要点都是确保不会出现这样的情况: 一边有一百万个节点，另一边有三个节点。多纳尔的定义在理论上是很好的，但在实践中，提出一个满足这种严格程度的树平衡算法是一件痛苦的事情。性能节省通常不能证明实现成本的合理性。你花了很多时间做不必要的树的重新安排，以达到一个平衡的水平，在实践中几乎没有什么区别。谁在乎有时需要四十个枝条才能到达一棵百万节不完全平衡的树上最远的叶子，而理论上一棵完全平衡的树只需要二十个枝条？重点是不需要一百万。从最坏的情况下一百万降到最坏的情况下四十通常是足够好的; 你不必一直走到最佳情况。

小开

下面是一个基于通用深度优先遍历的版本。应该比其他正确答案更快，并处理所有提到的“挑战”不好意思，我不太懂 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 );
}

小开

额外的锻炼反应。简单的解决办法。显然，在实际的实现中，可以包装这个或者其他东西，以避免要求用户在响应中包含身高。

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

小开

Here's what i have tried for Eric's bonus exercise. 我尝试解除我的递归循环，一旦我发现一个子树不平衡就返回。

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
}

小开

平衡是一个非常微妙的属性; 你认为你知道它是什么，但是很容易出错。特别是，甚至连埃里克•利伯特(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。然而，整个树是 A1平衡，因为有一个高度的差异2之间的 C和 F。您需要一个极小极大规范(尽管实际的算法可以不那么复杂，因为应该只有两个允许的高度)。

小开

事情比实际情况要复杂得多。

算法如下:

设 A = 最高级别节点的深度
设 B = 最低级节点的深度
如果 abs (A-B) < = 1，则树是平衡的

小开

The definition of a height-balanced binary tree is:

属性的高度的二叉树每个节点的两个子树 differ by more than 1.

空的二叉树总是高度平衡的。
A non-empty binary tree is height-balanced if:

它的左边子树是高度平衡的。
Its right subtree is height-balanced.
身高之间的差别左右子树不大 than 1.

Consider the tree:

    A
\
B
/ \
C   D

如图所示，A的左侧子树是高度平衡的(因为它是空的) ，它的右侧子树也是如此。但由于左子树的高度为 0，右子树的高度为 2，因此不满足条件3，树的高度仍然不平衡。

此外，下面的树是不平衡的高度，即使左侧和右侧子树的高度是相等的。您现有的代码将为其返回 true。

       A
/  \
B    C
/      \
D        G
/          \
E            H

So the word 每个 in the def is very important.

这将奏效:

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);
}

Ideone Link

小开

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));
}

小开

#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;
}

小开

    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;
}
}
}

小开

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;
}

小开

一个空树是高度平衡的。一个非空的二叉树 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)

小开

为了在巨大的树上获得更好的性能，你可以保存每个节点的高度，这样就可以在空间和性能之间进行权衡:

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;


}

小开

后订单解决方案，遍历树只有一次。时间复杂度为 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);
}
}

小开

Note 1: The height of any sub-tree is computed only once.

注意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;
}

小开

If binary tree is balanced or not can be checked by 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;
}

小开

下面是一个完整的 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);
}
}
}
}

小开

R:@Lucky 的解决方案，使用 BFS 进行层次顺序遍历。

我们遍历树并保留对 vars min/max-level 的引用，该引用描述了节点作为叶子的最小级别。

我认为“幸运的解决方案”需要修改。正如@code 所建议的，与其检查节点是否是叶子，我们必须检查左边或右边的子节点是否为空(不是两者都为空)。否则，算法会认为这是一个有效的平衡树:

在 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)空间运行。内存溢出将定向到堆，而不是发送递归调用堆栈。

或者，我们可以首先遍历树，迭代计算每个根子树的 + cache 最大高度。然后在另一个迭代运行中，检查每个根的左右子树的缓存高度是否不会有多于一个的差异。这也会在 O (n)时间和 O (n)空间中运行，但是会迭代，以避免引起堆栈溢出。

小开

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");
}
}

小开

递归地检查每个子树是否平衡。递归意味着，你要求子树和子树将返回一个响应。你一直问，直到问到最基本的。在树问题的基本情况是当你击中叶节点。

在这种情况下，我们向子树提出两个问题:

你平衡吗？

你的身高是多少？

所以递归函数会返回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]

this is javascript code:

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]
};

小开

a height-balanced binary tree is a binary tree in which the depth of the two subtrees of each node does not differ by more than one

这是树节点

public class TreeNode
{
public int Value;
public TreeNode Left;
public TreeNode Right;


public TreeNode(int value)
{
Value = value;
}
}

    public bool IsBalanced(TreeNode root)
{
if(root == null)
{
return true;
}
        

var left = Depth(root.Left);
var right = Depth(root.Right);
        

if(Math.Abs(left - right) > 1)
{
return false;
}
        

return IsBalanced(root.Left) && IsBalanced(root.Right);
}
    

private int Depth(TreeNode node)
{
if(node == null)
{
return 0;
}
return Math.Max(Depth(node.Left), Depth(node.Right)) + 1;
}

你可以试着练习给你