c++ - 二叉搜索树的最大深度

Question

我想找到二叉搜索树的最大深度。我找到了一个代码。

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 ？

是默认的吗？代码很简单，但我不知道答案从何而来，谁能解释一下？

Answer 1

给定这棵树:

[一]

/\

[B] [C]

对于带 NULL 的 [B] 和带 NULL 的 [C] 将调用 maxDepth，两者都返回零，因此递归调用最终返回 0+1。

如果 [C] 下有一个节点 [D]，那么对 [D] maxDepth 的调用将返回 NULL，D 将返回 0+1，然后递归将继续扩大，[C] 将收到 0+1并将一些 +1，返回 maxDepth 2，它大于包含 [B] 的分支的深度，即 1，因此从完整递归返回 maxDepth 2。