blocks|key|1368652|text|这只确定树的顶层是否平衡。也就是说，你可以有一棵树，在最左边和最右边有两个长分支，中间没有任何东西，这将返回true。在返回true之前，您需要递归地检查root.left和root.right，看看它们在内部是否也是平衡的。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|1368653|entityMap^0|25|9|2F|A|0^^$0|@$1|2|3|4|5|6|7|H|8|@$9|I|A|J|B|C]|$9|K|A|L|B|C]]|D|@]|E|$]]|$1|F|3|-4|5|6|7|M|8|@]|D|@]|E|$]]]|G|$]]

This only determines if the top level of the tree is balanced. That is, you could have a tree with two long branches off the far left and far right, with nothing in the middle, and this would return true. You need to recursively check the <code>root.left</code> and <code>root.right</code> to see if they are internally balanced as well before returning true.

blocks|key|1583786|text|你需要一种方法来确定左和右的高度，以及左和右是否平衡。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1583787|然后我就return+height(node->left)+==+height(node->right);|offset|length|style|CODE|1583788|关于编写height函数，请阅读：Understanding+recursion|1583789|entityMap|0|LINK|mutability|MUTABLE|url|https://stackoverflow.com/questions/717725/understanding-recursion/717839#717839^0|0|4|1D|0|4|6|H|N|0|0^^$0|@$1|2|3|4|5|6|7|R|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|S|8|@$D|T|E|U|F|G]]|9|@]|A|$]]|$1|H|3|I|5|6|7|V|8|@$D|W|E|X|F|G]]|9|@$D|Y|E|Z|1|10]]|A|$]]|$1|J|3|-4|5|6|7|11|8|@]|9|@]|A|$]]]|K|$L|$5|M|N|O|A|$P|Q]]]]

Well, you need a way to determine the heights of left and right, and if left and right are balanced.

And I'd just <code>return height(node-&gt;left) == height(node-&gt;right);</code>

As to writing a <code>height</code> function, read:
<a href="https://stackoverflow.com/questions/717725/understanding-recursion/717839#717839">Understanding recursion</a>

blocks|key|1368714|text|你说的是哪种树？外面有很多self-balancing树。检查他们的算法，确定是否需要重新排序树以保持平衡。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1368715|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree^0|D|E|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@$A|M|B|N|1|O]]|C|$]]|$1|D|3|-4|5|6|7|P|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]]]

What kind of tree are you talking about? There are <a href="http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree" rel="nofollow noreferrer">self-balancing</a> trees out there. Check their algorithms where they determine if they need to reorder the tree in order to maintain balance.

blocks|key|1583854|text|平衡通常取决于每个方向上最长路径的长度。上面的算法不会为你做到这一点。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1583855|您尝试实现的是什么？周围有自平衡树(AVL/红黑)。事实上，Java树是平衡的。|1583856|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|F|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|G|8|@]|9|@]|A|$]]|$1|D|3|-4|5|6|7|H|8|@]|9|@]|A|$]]]|E|$]]

Balancing usually depends on the length of the longest path on each direction. The above algorithm is not going to do that for you.

What are you trying to implement? There are self-balancing trees around (AVL/Red-black).
In fact, Java trees are balanced.

blocks|key|1368803|text|平衡的意思有点取决于手头的结构。例如，B-Tree的节点不能超过从根到根的一定深度，或者更少，所有数据都位于从根到根的固定深度，但如果叶子到叶子的分布是不均匀的，则B-Tree可能会失衡。跳过列表根本没有平衡的概念，而是依靠概率来实现良好的性能。Fibonacci树故意失去平衡，推迟重新平衡以实现优越的渐近性能，以换取偶尔更长的更新。AVL和红黑树将元数据附加到每个节点，以实现深度平衡不变量。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1368804|所有这些结构以及更多的结构都存在于大多数常见编程系统的标准库中(除了python、RAGE!)。实现一两个是很好的编程实践，但这可能不是一个很好的利用您自己的时间用于生产的方法，除非您的问题有一些特殊的性能需求，而任何现成的集合都无法满足这些需求。|1368805|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|F|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|G|8|@]|9|@]|A|$]]|$1|D|3|-4|5|6|7|H|8|@]|9|@]|A|$]]]|E|$]]

What balanced means depends a bit on the structure at hand. For instance, A B-Tree cannot have nodes more than a certain depth from the root, or less for that matter, all data lives at a fixed depth from the root, but it can be out of balance if the distribution of leaves to leaves-but-one nodes is uneven. Skip-lists Have no notion at all of balance, relying instead on probability to achieve decent performance. Fibonacci trees purposefully fall out of balance, postponing the rebalance to achieve superior asymptotic performance in exchange for occasionally longer updates. AVL and Red-Black trees attach metadata to each node to attain a depth-balance invariant. 

All of these structures and more are present in the standard libraries of most common programming systems (except python, RAGE!). Implementing one or two is good programming practice, but its probably not a good use of time to roll your own for production, unless your problem has some peculiar performance need not satisfied by any off-the-shelf collections.

blocks|key|1583979|text|这不是可行的吗？|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1583980|return+(+(+Math.abs(+size(+root.left+)+-+size(+root.right+)+)+<+2+);|code-block|syntax|javascript|1583981|任何不平衡的树都会失败这一点。|1583982|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|K|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|L|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|M|8|@]|9|@]|A|$]]|$1|I|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|J|$]]

Wouldn't this work?

<pre><code>return ( ( Math.abs( size( root.left ) - size( root.right ) ) &lt; 2 );
</code></pre>

Any unbalanced tree would always fail this.

blocks|key|1368899|text|这是一个基于通用深度优先遍历的版本。应该比其他正确答案更快，并处理所有提到的“挑战”。很抱歉我的风格，我不是很懂Java。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1368900|如果max和min都被设置，并且两者的差值大于1，那么您仍然可以通过提前返回来使它更快。|1368901|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+%7C%7C+root.right+==+null+)+{
++++++++++++maxLeaf+=+max(+maxLeaf,+curDepth+);
++++++++++++minLeaf+=+min(+minLeaf,+curDepth+);
++++++++}
++++++++if+(+root.left+!=+null+)+{
++++++++++++curDepth+%2B=+1;
++++++++++++root+=+root.left;
++++++++}+else+{
++++++++++++Node+last+=+root;
++++++++++++while+(+root+!=+null
+++++++++++++&&+(+root.right+==+null+%7C%7C+root.right+==+last+)+)+{
++++++++++++++++curDepth+-=+1;
++++++++++++++++last+=+root;
++++++++++++++++root+=+root.parent;
++++++++++++}
++++++++++++if+(+root+!=+null+)+{
++++++++++++++++curDepth+%2B=+1;
++++++++++++++++root+=+root.right;
++++++++++++}
++++++++}
++++}
++++return+(+maxLeaf+-+minLeaf+<=+1+);
}|code-block|syntax|javascript|1368902|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|K|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|L|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|M|8|@]|9|@]|A|$G|H]]|$1|I|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|J|$]]

Here is a version based on a generic depth-first traversal. Should be faster than the other correct answer and handle all the mentioned "challenges." Apologies for the style, I don't really know Java.

You can still make it much faster by returning early if max and min are both set and have a difference >1.

<pre><code>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
 &amp;&amp; ( root.right == null || root.right == last ) ) {
 curDepth -= 1;
 last = root;
 root = root.parent;
 }
 if ( root != null ) {
 curDepth += 1;
 root = root.right;
 }
 }
 }
 return ( maxLeaf - minLeaf &lt;= 1 );
}
</code></pre>

blocks|key|1368982|text|额外的运动反应。简单的解决方案。显然，在实际的实现中，人们可能会包装这个或其他东西，以避免要求用户在响应中包含高度。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1368983|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)%2B1
++++return+balance+and+abs(heightleft+-+heightright)+<=+1+++++|code-block|syntax|javascript|1368984|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

Bonus exercise response. The simple solution. Obviously in a real implementation one might wrap this or something to avoid requiring the user to include height in their response.
<pre><code>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) &lt;= 1 
</code></pre>

blocks|key|1369033|text|以下是我为Eric的奖金练习所做的尝试。我试图解开我的递归循环，一旦我发现一个子树不平衡就返回。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1369034|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+%7C%7C+!+*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+%2B1+:+rb+%2B+1);+//+return+the+current+height+of+the+subtree
}|code-block|syntax|javascript|1369035|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

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.

<pre><code>int heightBalanced(node *root){
 int i = 1;
 heightBalancedRecursive(root, &amp;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 -&gt; left,i);

 if (!*i) // subtree is not balanced. Skip traversing the tree anymore
 return 0;

 rb = heightBalancedRecursive(root -&gt; right,i)

 if (abs(lb - rb) &gt; 1) // not balanced. Make i zero.
 *i = 0;

 return ( lb &gt; rb ? lb +1 : rb + 1); // return the current height of the subtree
}
</code></pre>

blocks|key|1369049|text|public+boolean+isBalanced(TreeNode+root)
{
++++return+(maxDepth(root)+-+minDepth(root)+<=+1);
}

public+int+maxDepth(TreeNode+root)
{
++++if+(root+==+null)+return+0;

++++return+1+%2B+max(maxDepth(root.left),+maxDepth(root.right));
}

public+int+minDepth+(TreeNode+root)
{
++++if+(root+==+null)+return+0;

++++return+1+%2B+min(minDepth(root.left),+minDepth(root.right));
}|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|1369050|unstyled|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|G|8|@]|9|@]|A|$B|C]]|$1|D|3|-4|5|E|7|H|8|@]|9|@]|A|$]]]|F|$]]

<pre><code>public boolean isBalanced(TreeNode root)
{
 return (maxDepth(root) - minDepth(root) &lt;= 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));
}
</code></pre>

blocks|key|1584231|text|#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+)
++++++++{
++++++++++++%2B%2Bnode_count;
++++++++}

++++++++++++++++if+(+current->left+)
++++++++++++++++{
++++++++++++++++++++++++q1.push(current->left);
++++++++++++++++++++++++q2.push(level+%2B+1);
++++++++++++++++}

++++++++++++++++if+(+current->right+)
++++++++++++++++{
++++++++++++++++++++++++q1.push(current->right);
++++++++++++++++++++++++q2.push(level+%2B+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;
}|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|1584232|unstyled|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|G|8|@]|9|@]|A|$B|C]]|$1|D|3|-4|5|E|7|H|8|@]|9|@]|A|$]]]|F|$]]

<pre><code>#include &lt;iostream&gt;
#include &lt;deque&gt;
#include &lt;queue&gt;

struct node
{
 int data;
 node *left;
 node *right;
};

bool isBalanced(node *root)
{
 if ( !root)
 {
 return true;
 }

 std::queue&lt;node *&gt; q1;
 std::queue&lt;int&gt; 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-&gt;left )
 {
 q1.push(current-&gt;left);
 q2.push(level + 1);
 }

 if ( current-&gt;right )
 {
 q1.push(current-&gt;right);
 q2.push(level + 1);
 }

 if ( level != last_level )
 {
 std::cout &lt;&lt; "Check: " &lt;&lt; (node_count ? node_count - 1 : 1) &lt;&lt; ", Level: " &lt;&lt; level &lt;&lt; ", Old level: " &lt;&lt; last_level &lt;&lt; std::endl;
 if ( level &amp;&amp; (node_count - 1) != (1 &lt;&lt; (level-1)) )
 {
 return false;
 }

 last_level = q2.front();
 if ( level ) node_count = 1;
 }
 }

 return true;
}

int main()
{
 node tree[15];

 tree[0].left = &amp;tree[1];
 tree[0].right = &amp;tree[2];
 tree[1].left = &amp;tree[3];
 tree[1].right = &amp;tree[4];
 tree[2].left = &amp;tree[5];
 tree[2].right = &amp;tree[6];
 tree[3].left = &amp;tree[7];
 tree[3].right = &amp;tree[8];
 tree[4].left = &amp;tree[9]; // NULL;
 tree[4].right = &amp;tree[10]; // NULL;
 tree[5].left = &amp;tree[11]; // NULL;
 tree[5].right = &amp;tree[12]; // NULL;
 tree[6].left = &amp;tree[13];
 tree[6].right = &amp;tree[14];
 tree[7].left = &amp;tree[11];
 tree[7].right = &amp;tree[12];
 tree[8].left = NULL;
 tree[8].right = &amp;tree[10];
 tree[9].left = NULL;
 tree[9].right = &amp;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 &lt;&lt; "Result: " &lt;&lt; isBalanced(tree) &lt;&lt; std::endl;

 return 0;
}
</code></pre>

blocks|key|1584288|text|++++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;
++++++++}
++++}
}|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|1584289|unstyled|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|G|8|@]|9|@]|A|$B|C]]|$1|D|3|-4|5|E|7|H|8|@]|9|@]|A|$]]]|F|$]]

<pre><code> static boolean isBalanced(Node root) {
 //check in the depth of left and right subtree
 int diff = depth(root.getLeft()) - depth(root.getRight());
 if (diff &lt; 0) {
 diff = diff * -1;
 }
 if (diff &gt; 1) {
 return false;
 }
 //go to child nodes
 else {
 if (root.getLeft() == null &amp;&amp; root.getRight() == null) {
 return true;
 } else if (root.getLeft() == null) {
 if (depth(root.getRight()) &gt; 1) {
 return false;
 } else {
 return true;
 }
 } else if (root.getRight() == null) {
 if (depth(root.getLeft()) &gt; 1) {
 return false;
 } else {
 return true;
 }
 } else if (root.getLeft() != null &amp;&amp; root.getRight() != null &amp;&amp; isBalanced(root.getLeft()) &amp;&amp; isBalanced(root.getRight())) {
 return true;
 } else {
 return false;
 }
 }
}
</code></pre>

blocks|key|1584331|text|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%2B1:r%2B1);

}}
public+boolean+balanced(Node+n){

++++int+l=+height(n.leftChild);
++++int+r=+height(n.rightChild);

++++System.out.println(l+%2B+"+"+%2Br);
++++if(Math.abs(l-r)>1)
++++++++return+false;
++++else+
++++++++return+true;
++++}|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|1584332|unstyled|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|G|8|@]|9|@]|A|$B|C]]|$1|D|3|-4|5|E|7|H|8|@]|9|@]|A|$]]]|F|$]]

<pre><code>public int height(Node node){
 if(node==null)return 0;
 else{
 int l=height(node.leftChild);
 int r=height(node.rightChild);
 return(l&gt;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)&gt;1)
 return false;
 else 
 return true;
 }
</code></pre>

blocks|key|1369238|text|空树的高度是平衡的。非空二叉树T是平衡的，如果：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1369239|1)+T的左子树是平衡的|1369240|2)+T的右子树是平衡的|1369241|3)左右子树的高度差不大于1。|1369242|/*+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)+%2B+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)+%7C%7C+(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;
}|code-block|syntax|javascript|1369243|时间复杂度:+O(n)|1369244|entityMap^0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|Q|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|R|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|S|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|T|8|@]|9|@]|A|$]]|$1|H|3|I|5|J|7|U|8|@]|9|@]|A|$K|L]]|$1|M|3|N|5|6|7|V|8|@]|9|@]|A|$]]|$1|O|3|-4|5|6|7|W|8|@]|9|@]|A|$]]]|P|$]]

An empty tree is height-balanced. A non-empty binary tree T is balanced if:

1) Left subtree of T is balanced

2) Right subtree of T is balanced

3) The difference between heights of left subtree and right subtree is not more than 1.

<pre><code>/* program to check if a tree is height-balanced or not */
#include&lt;stdio.h&gt;
#include&lt;stdlib.h&gt;
#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 --&gt; Height of left subtree 
 rh --&gt; 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-&gt;left, &amp;lh);
 r = isBalanced(root-&gt;right,&amp;rh);

 /* Height of current node is max of heights of left and 
 right subtrees plus 1*/ 
 *height = (lh &gt; 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 &gt;= 2) || (rh - lh &gt;= 2))
 return 0;

 /* If this node is balanced and left and right subtrees 
 are balanced then return true */
 else return l&amp;&amp;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-&gt;data = data;
 node-&gt;left = NULL;
 node-&gt;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-&gt;left = newNode(2);
 root-&gt;right = newNode(3);
 root-&gt;left-&gt;left = newNode(4);
 root-&gt;left-&gt;right = newNode(5);
 root-&gt;right-&gt;left = newNode(6);
 root-&gt;left-&gt;left-&gt;left = newNode(7);

 if(isBalanced(root, &amp;height))
 printf("Tree is balanced");
 else
 printf("Tree is not balanced"); 

 getchar();
 return 0;
}
</code></pre>

Time Complexity: O(n)

blocks|key|1369299|text|为了有更好的性能，特别是在大树上，你可以保存每个节点的高度，所以这是一个空间和性能的权衡：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1369300|class+Node+{
++++Node+left;
++++Node+right;
++++int+value;
++++int+height;
}|code-block|syntax|javascript|1369301|实现相加和删除相同的示例|1369302|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+%2B=+1;
+++++++++height%2B%2B;
+++++++++else+if(v+>+root.value){
++++++++++++root+=+root.left();
++++++++++++}
+++++++++else{
+++++++++root+=+root.right();
+++++++++}

+++++}

+++++++++height%2B%2B;
+++++++++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+%7C%7C+isTreeBalanced(root.left)+&&+isTreeBalanced(root.right)+&&+isNodeBlanced(root))
++++return+true;

++return+false;

}|1369303|entityMap^0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|M|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|N|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|O|8|@]|9|@]|A|$]]|$1|I|3|J|5|D|7|P|8|@]|9|@]|A|$E|F]]|$1|K|3|-4|5|6|7|Q|8|@]|9|@]|A|$]]]|L|$]]

To have a better performance specially on huge trees you can save the height in each node so it is a trade off space Vs performance:

<pre><code>class Node {
 Node left;
 Node right;
 int value;
 int height;
}
</code></pre>

Example of implementing the addition and same for deletion 

<pre><code>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 &gt; 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) &gt; 2)
 return false;

 return true;
}

Boolean isTreeBlanced (Node root)
{
 if(root == null || isTreeBalanced(root.left) &amp;&amp; isTreeBalanced(root.right) &amp;&amp; isNodeBlanced(root))
 return true;

 return false;

}
</code></pre>

blocks|key|1369331|text|后订单解决方案，只遍历树一次。时间复杂度为O(n)，空间复杂度为O(1)，优于自顶向下求解。我给你一个java版本的实现。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1369332|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+%2B+Math.max(left,+right);
++++}
}|code-block|syntax|javascript|1369333|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

Post order solution, traverse the tree only once. Time complexity is O(n), space is O(1), it's better than top-down solution. I give you a java version implementation.

<pre><code>public static &lt;T&gt; boolean isBalanced(TreeNode&lt;T&gt; root){
 return checkBalance(root) != -1;
}

private static &lt;T&gt; int checkBalance(TreeNode&lt;T&gt; 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) &gt; 1){
 return -1;
 }else{
 return 1 + Math.max(left, right);
 }
}
</code></pre>

blocks|key|1584550|text|注1:任何子树的高度只计算一次。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1584551|注2:如果左子树不平衡，则跳过右子树的计算，可能包含百万个元素。|1584552|//+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+%2B+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;
}|code-block|syntax|javascript|1584553|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|K|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|L|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|M|8|@]|9|@]|A|$G|H]]|$1|I|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|J|$]]

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

Note 2: If the left sub-tree is unbalanced then the computation of the right sub-tree, potentially containing million elements, is skipped.

<pre><code>// 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-&gt;left );
 if( lh == -1 ) return -1;
 int const rh = maxHeight( tn-&gt;right );
 if( rh == -1 ) return -1;
 if( abs( lh - rh ) &gt; 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;
}
</code></pre>

blocks|key|1584583|text|如果二叉树是平衡的，可以通过级别顺序遍历来检查：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1584584|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%2B%2B;
++++}

++++return+true;
}|code-block|syntax|javascript|1584585|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

If binary tree is balanced or not can be checked by Level order traversal:

<pre><code>private boolean isLeaf(TreeNode root) {
 if (root.left == null &amp;&amp; root.right == null)
 return true;
 return false;
}

private boolean isBalanced(TreeNode root) {
 if (root == null)
 return true;
 Vector&lt;TreeNode&gt; queue = new Vector&lt;TreeNode&gt;();
 int level = 1, minLevel = Integer.MAX_VALUE, maxLevel = Integer.MIN_VALUE;
 queue.add(root);
 while (!queue.isEmpty()) {
 int elementCount = queue.size();
 while (elementCount &gt; 0) {
 TreeNode node = queue.remove(0);
 if (isLeaf(node)) {
 if (minLevel &gt; level)
 minLevel = level;
 if (maxLevel &lt; 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) &gt; 1) {
 return false;
 }
 level++;
 }

 return true;
}
</code></pre>

blocks|key|1584659|text|这是一个完整的C#测试解决方案(对不起，我不是java开发人员)(只需在控制台应用程序中复制粘贴即可)。我知道平衡的定义是不同的，所以不是每个人都喜欢我的测试结果，但请看看在递归循环中检查深度/高度并在第一个不匹配时退出的略微不同的方法，而不在每个节点上保存节点高度/级别/深度(仅在函数调用中维护它)。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1584660|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+%7C%7C+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+%2B+":"+%2B+Count;
++++++++}

++++++++public+bool+IsLeafNode()
++++++++{
++++++++++++return+LeftChild+==+null+&&+RightChild+==+null;
++++++++}

++++++++public+void+AddValue(int+value)
++++++++{
++++++++++++if+(value+==+Value)
++++++++++++{
++++++++++++++++Count%2B%2B;
++++++++++++}
++++++++++++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%2B%2B;
++++++++++++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+%2B+",");
++++++++++++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+%2B+",");
++++++++++++sb.Append(node.RightChild+%2B+",");
++++++++++++if+(node.LeftChild+!=+null+&&+!node.LeftChild.IsLeafNode())
++++++++++++{
++++++++++++++++TraversBreadthWards(sb,+node.LeftChild);
++++++++++++}
++++++++++++if+(node.RightChild+!=+null+&&+!node.RightChild.IsLeafNode())
++++++++++++{
++++++++++++++++TraversBreadthWards(sb,+node.RightChild);
++++++++++++}
++++++++}
++++}
}|code-block|syntax|javascript|1584661|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

Here is a complete worked out tested solution in C# (sorry I'm no java dev) (just copy paste in console app).
I know that definition of balanced varies so not everyone may like my test results but please just look at the slightly different approach of checking depth/height in a recursive loop and exiting on the first mismatch without saving node height/level/depth on each node (only maintaining it in a function call).

<pre><code>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 &amp;&amp; RightChild == null;
 }

 public void AddValue(int value)
 {
 if (value == Value)
 {
 Count++;
 }
 else
 {
 if (value &gt; 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 &amp;&amp; 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 &amp;&amp; !node.LeftChild.IsLeafNode())
 {
 TraversBreadthWards(sb, node.LeftChild);
 }
 if (node.RightChild != null &amp;&amp; !node.RightChild.IsLeafNode())
 {
 TraversBreadthWards(sb, node.RightChild);
 }
 }
 }
}
</code></pre>

blocks|key|1369614|text|RE：@lucky的解决方案是使用BFS进行级别顺序遍历。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1369615|我们遍历树并保持对vars+min/max-level的引用，它描述了节点作为叶的最低级别。|1369616|我认为@lucky解决方案需要修改。正如@codaddict所建议的，我们必须检查左侧或右侧的子节点是否为空(而不是两个都为)，而不是检查节点是否是叶节点。否则，算法将认为这是一个有效的平衡树：|1369617|+++++1
++++/+\
+++2+++4
++++\+++\
+++++3+++1|code-block|syntax|javascript|1369618|在Python中：|1369619|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+%2B=+1

++++++++if+abs(max_level+-+min_level)+>+1:
++++++++++++return+False

++++return+True|1369620|这个解决方案应该满足初始问题中提供的所有规定，在O(n)时间和O(n)空间中运行。内存溢出将被定向到堆，而不是破坏递归调用堆栈。|1369621|或者，我们可以首先遍历树，迭代地计算每个根子树的最大缓存高度。然后，在另一次迭代运行中，检查每个根的左子树和右子树的缓存高度是否相差不超过一个。这也将在O(n)时间和O(n)空间内运行，但要迭代，以免导致堆栈溢出。|1369622|entityMap^0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|U|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|V|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|W|8|@]|9|@]|A|$]]|$1|F|3|G|5|H|7|X|8|@]|9|@]|A|$I|J]]|$1|K|3|L|5|6|7|Y|8|@]|9|@]|A|$]]|$1|M|3|N|5|H|7|Z|8|@]|9|@]|A|$I|J]]|$1|O|3|P|5|6|7|10|8|@]|9|@]|A|$]]|$1|Q|3|R|5|6|7|11|8|@]|9|@]|A|$]]|$1|S|3|-4|5|6|7|12|8|@]|9|@]|A|$]]]|T|$]]

RE: @lucky's solution using a BFS to do a level-order traversal.

We traverse the tree and keep a reference to vars min/max-level which describe the minimum level at which a node is a leaf.

I believe that the @lucky solution requires a modification. As suggested by @codaddict, rather than checking if a node is a leaf, we must check if EITHER the left or right children is null (not both). Otherwise, the algorithm would consider this a valid balanced tree:

<pre><code> 1
 / \
 2 4
 \ \
 3 1
</code></pre>

In Python:

<pre><code>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) &gt; 1:
 return False

 return True
</code></pre>

This solution should satisfy all the stipulations provided in the initial question, operating in O(n) time and O(n) space. Memory overflow would be directed to the heap rather than blowing a recursive call-stack.

Alternatively, we could initially traverse the tree to compute + cache max heights for each root subtree iteratively. Then in another iterative run, check if the cached heights of the left and right subtrees for each root never differ by more than one. This would also run in O(n) time and O(n) space but iteratively so as not to cause stack overflow.

blocks|key|1369630|text|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+%2B+Math.max(maxDepth(node.left),+maxDepth(node.right));
++++}

++++//+get+min+depth
++++public+static+int+minDepth(Node+node)+{
++++++++if+(node+==+null)
++++++++++++return+0;

++++++++return+1+%2B+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");
++++}
}|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|1369631|unstyled|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|G|8|@]|9|@]|A|$B|C]]|$1|D|3|-4|5|E|7|H|8|@]|9|@]|A|$]]]|F|$]]

<pre><code>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&lt;=1 to check if tree balanced
 public boolean isBalanced(Node node) {

 if (Math.abs(maxDepth(node) - minDepth(node)) &lt;= 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");
 }
}
</code></pre>

blocks|key|1369708|text|递归地检查每个子树是否平衡。递归意味着，您向子树发出请求，子树将返回响应。你一直在问直到你找到了最基本的情况。在树问题中，基本大小写是当你命中叶节点时。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1369709|在这种情况下，我们向子树提出两个问题：|1369710|1-你平衡了吗？|1369711|2-你的身高是多少？|1369712|因此递归函数将返回2个答案，我将这些答案保存在数组中。|1369713|这是python代码：|1369714|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%2Bmax(left[1],right[1])+is+the+height+of+the+each+subtree.+1+is+the+root+of+the+subtree
++++++++++++return+[balanced,1%2Bmax(left[1],right[1])]
++++++++return+dfs(root)[0]|code-block|syntax|javascript|1369715|这是javascript代码：|1369716|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%2BMath.max(left[1],right[1])]
+}
++++return+dfs(root)[0]
};|1369717|entityMap^0|0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|W|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|X|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|Y|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|Z|8|@]|9|@]|A|$]]|$1|H|3|I|5|6|7|10|8|@]|9|@]|A|$]]|$1|J|3|K|5|6|7|11|8|@]|9|@]|A|$]]|$1|L|3|M|5|N|7|12|8|@]|9|@]|A|$O|P]]|$1|Q|3|R|5|6|7|13|8|@]|9|@]|A|$]]|$1|S|3|T|5|N|7|14|8|@]|9|@]|A|$O|P]]|$1|U|3|-4|5|6|7|15|8|@]|9|@]|A|$]]]|V|$]]

Recursively check if each subtree is balanced or not. Recursion means, you ask something to subtree and subtree will return a response. You keep asking till you hit the base case. in tree questions base case is when you hit the leaf node.
In this case, we ask 2 questions to a subtree:
1- Are you balanced?
2- What is your height?
So recursive function will return 2 answers, and I keep those answers in the array.
This is python code:
<pre><code>class Solution:
 def isBalanced(self, root: Optional[TreeNode]) -&gt; 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])&lt;=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]
</code></pre>
this is javascript code:
<pre><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] &amp;&amp; right[0] &amp;&amp; Math.abs(left[1]-right[1])&lt;=1
 return [balanced,1+Math.max(left[1],right[1])]
 }
 return dfs(root)[0]
};
</code></pre>

It's been a while from those school years. Got a job as IT specialist at a hospital. Trying to move to do some actual programming now. I'm working on binary trees now, and I was wondering what would be the best way to determine if the tree is height-balanced. 

I was thinking of something along this:

<pre><code>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 &gt; 1 || rh - lh &gt; 1){
 return false;
 }
 }
 return true;
}
</code></pre>

Is this a good implementation? or am I missing something?

How to determine if binary tree is balanced?

Python

Java

已经有一段时间没有学生时代了。在一家医院找到了一份IT专家的工作。现在我正试着去做一些实际的编程。我现在正在研究二叉树，我想知道确定树是否高度平衡的最好方法是什么。我一直在想这样的事情：public boolean isBalanced(Node root){    if(root==null){        ret...

问如何判断二叉树是否平衡？
EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问如何判断二叉树是否平衡？EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问如何判断二叉树是否平衡？
EN