[第二轮] 3/11-3/17 CareerCup 4.1

*  method1： calculate the height of every node....
*  method2: we don't need to calculate the height of every node....
the default leaf height  is zero......
https://github.com/1094401996/Ca ... ot1/IsBalanced.java

https://gist.github.com/ThunderXu/5174776
use recursion to calculate depth of leftchild and rightchild for every node

recursively find the maxDepth and minDepth, evaluate whether its balanced or not by the different of the minDepth and maxDepth

C++ implementation

https://github.com/StanleyLee/CareerCup/blob/master/4_1.cpp

recursively find the maxDepth and minDepth, evaluate whether its balanced or not by the different of the minDepth and maxDepth

C++ implementation

https://github.com/StanleyLee/CareerCup/blob/master/4_1.cpp

weep_willow 发表于 2013-3-17 12:19
recursively find the maxDepth and minDepth, evaluate whether its balanced or not by the different of ...

平衡，仅仅考察根节点是不够的，需要每个节点都要考察。如下case
------------------a
--------------b------c
--------d---------------e
----f
只有根节点满足最大最小深度相差不超过1.

sing1ee 发表于 2013-3-17 23:11
平衡，仅仅考察根节点是不够的，需要每个节点都要考察。如下case
------------------a
--------------b ...

谢谢你的回复，我觉得你给的这种情况可以判断是不平衡啊
我手动递归的推了一下 maxDepth=4, minDepth=2， 4-2>1, 所以程序返回应该为不平衡， 我觉得没有问题啊

weep_willow 发表于 2013-3-18 23:09
谢谢你的回复，我觉得你给的这种情况可以判断是不平衡啊
我手动递归的推了一下 maxDepth=4, minDepth=2， ...

我的例子举得不对=.=

看看百科这个例子。按照你的思路，是不是maxDepth=5, minDepth=3？

sing1ee 发表于 2013-3-19 09:59
我的例子举得不对=.=

我觉得是啊 所以不是balanced啊

https://gist.github.com/Jnight/5271745 求拍砖，有加分