b*****s
发帖数: 36 | 1 我一直有个问题比较confused：
height-balanced 的定义到底是以下哪一种：
（1）Wikipedia上说：A balanced binary tree is commonly defined as a binary
tree in which the depth of the two subtrees of every node never differ by
more than 1。
（2）careercup书和Leetcode的balanced tree相关的题目上如此定义：A height-
balanced tree is a tree whose subtrees differ in height by no more than one
and the subtrees are height-balanced, too.
也就是说以下这个tree是符合（2）的要求而不符合（1）的要求。
1
/ \
2 2
/ \ / \
3 3 3 3
/\ /\ /\
4 4 4 4 4 4
/\
5 5
我们面试的时候一般遵循哪一种定义呢？还是应该向面试官问清楚balanced的定义？
谢谢。 |
C***U
发帖数: 2406 | 2 我了解的定义 比一定对
就是root到叶子的路径长度差小于一个数。比如小于1 或者最长的比最短不能超过2倍
之类的
one
【在 b*****s 的大作中提到】
: 我一直有个问题比较confused：
: height-balanced 的定义到底是以下哪一种：
: （1）Wikipedia上说：A balanced binary tree is commonly defined as a binary
: tree in which the depth of the two subtrees of every node never differ by
: more than 1。
: （2）careercup书和Leetcode的balanced tree相关的题目上如此定义：A height-
: balanced tree is a tree whose subtrees differ in height by no more than one
: and the subtrees are height-balanced, too.
: 也就是说以下这个tree是符合（2）的要求而不符合（1）的要求。
: 1
|
C***U
发帖数: 2406 | 3 就是说可以自己规定balance的lavel吧。
one
【在 b*****s 的大作中提到】
: 我一直有个问题比较confused：
: height-balanced 的定义到底是以下哪一种：
: （1）Wikipedia上说：A balanced binary tree is commonly defined as a binary
: tree in which the depth of the two subtrees of every node never differ by
: more than 1。
: （2）careercup书和Leetcode的balanced tree相关的题目上如此定义：A height-
: balanced tree is a tree whose subtrees differ in height by no more than one
: and the subtrees are height-balanced, too.
: 也就是说以下这个tree是符合（2）的要求而不符合（1）的要求。
: 1
|
l****c
发帖数: 782 | 4 没看懂为什么不满足2。。。
你是说你树上标的数字是height吗？如果那样的话，啥树都满足了。 |
g****y
发帖数: 240 | 5 为什么不符合（1）？感觉（1）和（2）是一回事儿。 |
b*********h
发帖数: 103 | 6 平衡树有很多种，性质也不同
CareerCup 上说的是 AVL
2 楼想说的可能是 Red-Black
感觉如果问这个问题 可以说些公有的性质和思想 如果直接默认 interviewers 说的是
什么树，并且说它的性质可能不是他们想要的。或者提问后谈一种自己熟悉的 |
b*****s
发帖数: 36 | 7 我这里树上标的数字没有实际意义。
我的意思是，这个tree符合（2）的定义却不符合（1）的定义。（2）允许不同subtree
的leaf之间height之差大于1，而（1）不允许。
【在 l****c 的大作中提到】
: 没看懂为什么不满足2。。。
: 你是说你树上标的数字是height吗？如果那样的话，啥树都满足了。
|
l****c
发帖数: 782 | 8 哦，我是觉得（2）也不符合
subtree
【在 b*****s 的大作中提到】
: 我这里树上标的数字没有实际意义。
: 我的意思是，这个tree符合（2）的定义却不符合（1）的定义。（2）允许不同subtree
: 的leaf之间height之差大于1，而（1）不允许。
|
x*********n
发帖数: 46 | 9 我怎么看这个tree （１）和（２）都符合？
对于任何一个节点，左子树的高度和右子树高度差不超过1, 没看出为什么楼主说不符
合(1). |
n******n
发帖数: 567 | 10 这样的算是么？
1
/ \
2 2
/ \
3 3
/ \
4 4
/
5 |
h****e
发帖数: 928 | 11 这个绝对是要向面试你的人问清楚的。
自己准备时两种（或者更多）定义的balanced判断都要写出来。 |
