二分木の高さを求める
ある二分木が与えられたとき、その高さを求めてください。ここで二分木の高さとは、根ノードの高さのことで、根ノードの下にあるノードの層の最大数を指します。
右側の例では:
値が4、6、7、8のノードは高さ1
値が3、5のノードは高さ2
値が2のノードは高さ3
値が1の根ノードは高さ4
入力
入力として、二分木のノードの値を空白区切りの整数で与えます。各値は、左部分木から右部分木へと順番にたどったときの並びを表します。値が0の場合、そのノードが存在しないことを意味します。入力の二分木は有効であることが保証されています。
出力
プログラムは、与えられた二分木の高さを出力してください。
例
入力 | 出力 |
|---|---|
1 2 3 8 5 0 0 0 0 5 8 0 0 0 0 | 3 |
1 2 3 4 5 0 0 7 8 0 0 0 0 0 6 0 0 | 4 |
解説
例 1:
例 2:
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB