提问人：Amanda James 提问时间：7/24/2022 最后编辑：trincotAmanda James 更新时间：7/25/2022 访问量：205
节点在二叉树中具有负高度意味着什么？
What does it mean for a node to have a negative height in a binary tree?
问：
我正在查看定义函数的代码，该函数返回二叉树中给定的高度。我不明白为什么它应该返回值 -1？高度为负是什么意思？heightTreeNode
int height(TreeNode root) {
// ...
int left = height(root.left);
int right = height(root.right);
if(left == -1 || right == -1) return -1;
}
答：
1赞
trincot
7/24/2022
#1
首先，在你原来的问题中，你写道：
当 TreeNode 的 int 值为 -1 时
我们在这里看到的不是节点的值，而是它的高度。该函数返回作为参数给出的节点的高度，而不是其值。现在在问题中更正了这一点。height
节点的高度定义为从该节点到树中任何树叶的最长路径的长度。举个例子，以这棵树为例：
17
/ \
5 31
\
8
值为 17 的节点的高度为 2，因为到叶的最长路径为 2（具有边 17-5 和边 5-8）。
值为 5 的节点的高度为 1，节点 31 和 8 的高度均为 0。
但是，当您调用一个参数时会发生什么？这时函数应返回 -1。这就像说“你沿着一条边走得太远了——你沿着一条不存在的边缘走”。heightnull
现在回到您的代码：
当 是 -1 时，表示 是 。逻辑表达式等效于 。和 也存在类似的等价关系。leftroot.leftnullleft == -1root.left == nullrightroot.right
这个函数的逻辑是错误的。当节点有效时，它不应返回 -1。如上所述，当给定节点 （） 本身时，它应该只返回 -1，但在这里我们看到当是叶节点时返回 -1 的代码（即 both 和 are ）。但在这种情况下，它应该返回 0，而不是 -1。heightrootrootnullrootroot.leftroot.rightnull
正确的函数可能如下所示：height
int height(TreeNode root) {
if (root == null) return -1; // This is the only case where we return -1
// The root's height is determined by the height of its children
int left = height(root.left);
int right = height(root.right);
// ...the child with the greatest height is determining it:
// we add one level to that height, which represents the root itself:
return 1 + Math.max(left, right);
}
评论
heightheight-1