A******g
发帖数: 612 | 1 题目：判断一个binary tree 是否平衡，平衡的定义是任意node，左边subtree和右边
subtree的高度相差不超过1。Careercup150有这道题，用了书上的解法。没有通过全部
测试。觉得careercup解法好像不对。
比如这个
{1,2,3,4,5,#,6,7}
1
/ \
2 3
/\ \
4 5 6
/
7
Careercup是用max depth - min depth = 3-1=2 不平衡
主要是上面的minDepth算法会把1右边substree算成2
请大牛指点！
careercup书上解法：
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int max_depth(TreeNode *root) {
if (root==NULL)
return 0;
return 1+max( max_depth(root->left), max_depth(root->right));
}
int min_depth(TreeNode *root) {
if (root==NULL)
return 0;
return 1+min( min_depth(root->left), min_depth(root->right));
}
bool isBalanced(TreeNode *root) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
return max_depth(root)-min_depth(root) <= 1;
}
}; | l*********8
发帖数: 4642 | 2 leetcode要求每个子树也都是banlanced tree. | A******g
发帖数: 612 | 3 CLRS也是这么定义的，我觉得careercup150的不对
【在 l*********8 的大作中提到】
: leetcode要求每个子树也都是banlanced tree.
| r*********n
发帖数: 4553 | 4 careercup150上面用leaf node的深度来定义平衡，我觉得这个定义不对。
如果一个树，包括所有子树，只有左child，这棵树的高度是n，显然不是log(n)，但是
用careercup150上面的定义，这棵树就是平衡的，因为只有一个leaf node。 | O******i
发帖数: 269 | 5 确实是CC150错了，是个伪定义。
用max depth - min depth <= 1来定义平衡，要求过于严格，实际上是充分而非必要条
件。你例子中那样的树虽然是平衡树但不满足该定义。
这种过于严格的定义必然导致false negative
【在 A******g 的大作中提到】
: 题目：判断一个binary tree 是否平衡，平衡的定义是任意node，左边subtree和右边
: subtree的高度相差不超过1。Careercup150有这道题，用了书上的解法。没有通过全部
: 测试。觉得careercup解法好像不对。
: 比如这个
: {1,2,3,4,5,#,6,7}
: 1
: / \
: 2 3
: /\ \
: 4 5 6
| f*******7
发帖数: 943 | 6 新版的150好像改过来了吧，而且这种歧义面试时需要和面试官确认的 |
|
