２分木の高さを求めるためのコードの書き方を教えてください！

Question

今、LeetCodeというサイトでアルゴリズム問題を解いているのですが、
二分木の高さを求める問題に苦戦しています。

以下問題です。

=====================================================================
Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Note: A leaf is a node with no children.

Example:

Given binary tree [3,9,20,null,null,15,7]

=====================================================================

考え方をおしえていただけたら幸いです！

よろしくお願いします！

以下追記
調べていたら、このような回答を見つけたのですが、
まったくもってコードの仕組みがわからないです。

def max_depth(root)
  root ? 1 + [max_depth(root.left), max_depth(root.right)].max : 0
end

Answer 1

追記に対してです。

子nodeに対して再帰で深さを取ってきて、大きい方を親に戻り値として返している処理ですね。
深さを見に行った時に、そのnodeが子nodeを持たない時はそれ以上深さを持たないので深さ0として戻り値を返しています。

これを繰り返すと、深さ優先探索で全探索するので一番上のrootに戻ってきた時に大きな深さが戻ってくる仕組みになっています。

Comments

[a.hamaaaaaaaa]

ありがとうございます！
たすかりました！

Answer 2

幅優先探索かな

[root] => [right,left] => [leftleft,leftright,rightleft,rightright]

こんな感じの再帰組むのが手っ取り早い

Comments

[a.hamaaaaaaaa]

回答有り難うございます。深度を出したいのですが、ご教示頂いた考え方でいいのでしょうか？
深さ優先探索というのもあるのですが、そちらかなと思いまして。

[asm]

どちらでも、お好みでどうぞ