我想找到二进制搜索树的最大深度 . 我找到了一个代码 .
int maxDepth(struct node* node) {
if (node==NULL) {
return(0);
}
else {
// compute the depth of each subtree
int lDepth = maxDepth(node->left);
int rDepth = maxDepth(node->right);
// use the larger one
if (lDepth > rDepth) return(lDepth+1);
else return(rDepth+1);
}
}
我想知道node-> left怎么会返回1?
这是默认的吗?代码很简单,但我不知道答案即将来临,有人可以解释一下吗?
2 回答
鉴于这棵树:
[一个]
/ \
[B] [C]
将使用NULL为[B]调用maxDepth,对于具有NULL的[C],将返回零,因此递归调用最终返回0 1 .
如果在[C]下有一个节点[D],那么对[D] maxDepth的调用将返回NULL而D将返回0 1,那么递归将继续按比例放大,[C]将接收0 1并且将为1,返回maxDepth为2,它大于保持[B]的分支的深度,该分支是1,因此从完全递归返回maxDepth为2 .
当
node
指向一个叶子时,它的node->left
和node->right
都是NULL
. 所以maxDepth()
都返回0
. 所以这个叶子的当前递归只返回深度0 + 1 = 1.
你可以证明它的正确性 .
Initialization
当节点为
NULL
时,它返回0
. 确实,空树的深度为0
. 当节点为leaf时,它返回1
. 刚刚解释过 .Maintenance
如果存在节点(不是
NULL
)并且我们知道其子节点的深度,则此节点的深度将为max(depth of left, depth of right) + 1
. 这就是回归 .Termination
它将终止,因为当它到达叶子时,递归将停止变深并返回 . 当整个递归完成时,
maxDepth(root)
返回root
的深度 .