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)和(2)都符合?
对于任何一个节点,左子树的高度和右子树高度差不超过1, 没看出为什么楼主说不符
合(1). |
n******n 发帖数: 567 | 10 这样的算是么?
1
/ \
2 2
/ \
3 3
/ \
4 4
/
5 |
h****e 发帖数: 928 | 11 这个绝对是要向面试你的人问清楚的。
自己准备时两种(或者更多)定义的balanced判断都要写出来。 |