LeetCode: Binary Tree-1

LeetCode

概要

LeetCodeを始めたのでその学習記録です。

Binary Tree

まえがき

『ツリー』とは、階層木構造を表すデータ構造である。 ツリーの各ノードは、ルート（根）と、子ノードと呼ばれる他のノードへの参照リストを持つ。 グラフ理論でいえば、ツリーは連結されていて閉路を持たないグラフであり、N個のノードとN-1個のエッジ（枝）を持つ。

バイナリツリーは、ツリーのもっとも典型的なものである。各ノードは多くて二個の子ノード（左と右）を持つ。

Traverse a Tree - Introduction

  • Pre-order Traversal ルートを訪問済みとして、左の子ノードを訪問していく。末端のノードにたどり着いたらそのルートノードに戻り、右から始まるサブツリーを、同じルールで探索する。根、左、右、の順。

  • In-order Traversal ルートを出発点にして、左のサブツリーから末端の左ノードを探索する。末端のノードにたどり着いたらそれを訪問済みとして、そのルートノードも訪問済みにし、次に右から始まるサブツリーを同じルールで探索する。左、根、右の順。 In-order Traversalを使うと、バイナリツリー内のソートされたデータを順序通り取得できる。

  • Post-order Traversal ルートを出発点にして、左のサブツリーから末端の左ノードを探索する。末端のノードにたどり着いたらそれを訪問済みとして、次にその同階層の右ノードから始まるサブツリーを同じルールで探索する。すべての子ノードが訪問済になったらルートも訪問済みにする。左、右、根の順。

例えば、ノードとその子ノードをツリーから削除しようとしたとき、対象ノードの子孫ノードは対象ノードの削除より前に削除されていなければならない。Post-order Traversalは、子孫ノードを先に訪問済みにできるので、このような処理に適している。 また、Post-order Traversalは、計算式を表現するのにも適している。