编写最短程序以检查二叉树是否平衡
编写最短程序以检查二叉树是否平衡
提问于 2019-08-05 17:14:34
对于平衡二叉树中的每个节点，左子树和右子树的高度的最大差异最多为1。
二叉树的高度是从根节点到离根最远的节点子节点的距离。
以下是一个例子：
2 <-- root: Height 1
/ \
7 5 <-- Height 2
/ \ \
2 6 9 <-- Height 3
/ \ /
5 11 4 <-- Height 4 二叉树高度:4
以下是二叉树和关于它们是否平衡的报告：
上面的树是<>不平衡的。
上面的树是平衡的。
编写尽可能最短的程序，接受二叉树的根作为输入，如果树不平衡，返回一个falsey值；如果树是平衡的，则返回一个真实值。
输入
二叉树的根。这可以是对根对象的引用，甚至可以是二叉树的有效表示形式的列表。
输出
Returns真实值：如果树是平衡的
Returns falsey值：如果树是un平衡的。
二叉树的Definition
树是一个对象，它包含一个值以及其他两个树或指向它们的指针。
二叉树的结构如下所示：
typedef struct T
{
struct T *l;
struct T *r;
int v;
}T;如果对二叉树使用列表表示，它可能如下所示：
[root_value, left_node, right_node]回答 8
Code Golf用户
发布于 2019-08-05 18:22:41
Prolog (SWI)，49字节
N+_/B/C:-X+B,Y+C,abs(X-Y)<2,N is max(X,Y)+1.
0+e.将树表示为Value/Left_Child/Right_Child，空树为原子e。定义+/2，它通过成功或失败输出，左边有一个未绑定变量(或一个已经等于树高的变量)，右边是树--如果高度参数是不可接受的，添加9个字节来定义-T:-_+T.。
N + _/B/C :- % If the second argument is a tree of the form _Value/B/C,
X+B, % X is the height of its left child which is balanced,
Y+C, % Y is the height of its right child which is balanced,
abs(X-Y) < 2, % the absolute difference between X and Y is strictly less than 2,
N is max(X,Y)+1. % and N is the height of the full tree.
0 + e. % If, on the other hand, the second argument is e, the first is 0.Code Golf用户
发布于 2019-08-06 02:51:43
JavaScript (Node.js)，49字节
h=([l,r])=>l?(d=h(l)-h(r))*d<2?1+h(d>0?l:r):NaN:1- Arnauld的9字节。
JavaScript，58字节
h=([l,r])=>l?(l=h(l),r=h(r),m=l>r?l:r,m+m-l-r<2?m+1:NaN):1对null使用[]，对节点使用[left, right, value]。
页面原文内容由Code Golf提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://codegolf.stackexchange.com/questions/189285
复制相关文章
相似问题
腾讯云开发者
