c++ - BST再帰的に高さを見つける

Question

私は自分のプログラムで二分探索木の高さを見つけようとしていますが、高さを見つけるためにこの再帰的な解決策を見つけ続けています:

int maxHeight(BinaryTree *p) {
  if (!p) return 0;
  int left_height = maxHeight(p->left);
  int right_height = maxHeight(p->right);
  return (left_height > right_height) ? left_height + 1 : right_height + 1;
}

誰かがこれがどのように機能するかを説明できますか? 高さを合計する方法がわかりません。ツリーの両側を通過して 0 を返すだけのようです。

Answer 1

あなたのコードはメモリに優しくありません。たとえば、このメソッドを実行すると、変数height_leftとheight_right変数はメモリに保存されたままになります。では、この関数を何十億回も実行するとどうなるでしょうか? たとえば、変数なしで返すことをお勧めします

return max(maxHeight(p->left), maxHeight(p->right));