Kotlin Binary Tree Preorder Traversal (再帰的なソリューションであり、再帰を使用しない場合)

この投稿は、バイナリ ツリーの事前順序トラバーサル、つまり現在のノードがその子の前にアクセスされるツリーをトラバースする方法に関するものです。事前順序トラバーサル アルゴリズムは、最初にルート ノードにアクセスし、次に再帰的に左のサブツリーにアクセスし、次に右のサブツリーにアクセスします。 preorder traversal の結果は、訪問された順序でのノードの値のリストです。この投稿は、バイナリ ツリーをトラバースする方法と、それをさまざまな方法で実装する方法を理解するのに役立ちます。

Preorder traversal は、現在のノードがその子の前にアクセスされる二分木を走査する方法です。このアルゴリズムは、最初にルート ノードにアクセスし、次に左のサブツリーに再帰的にアクセスし、次に右のサブツリーにアクセスします。 preorder traversal の結果は、訪問された順序でのノードの値のリストです。

この問題では、Kotlin のTreeNodeクラスで表されるバイナリ ツリーのルートが与えられます。これには、ノードの値のvalプロパティと、その左と右の子のそれぞれのleftとrightプロパティがあります。あなたの仕事は、バイナリ ツリーの事前順序トラバーサルを実行し、ノードの値のリストを返す関数の 2 つの実装を記述することです。 1 つは再帰的なソリューションであるべきで、もう 1 つは再帰を使用すべきではありません。

関数のクラス シグネチャは次のとおりです。

 fun preorderTraversal(root: TreeNode?): List<Int>

関数への入力はバイナリ ツリーのルート ノードであり、出力は事前順序探索中にアクセスされた順序でノードの値を表す整数のリストです。

説明:

バイナリ ツリーのルートを指定して、そのノードの値の事前順トラバーサルを返します。これは、再帰ソリューションを使用する場合と再帰を使用しない場合の両方で行います。

 class TreeNode(var `val`: Int) { var left: TreeNode? = null var right: TreeNode? = null }

問題の再帰的な解決策は次のとおりです。

 fun preorderTraversal(root: TreeNode?): List<Int> { val result = mutableListOf<Int>() if (root == null) return result result.add(root.val) result.addAll(preorderTraversal(root.left)) result.addAll(preorderTraversal(root.right)) return result }

この関数は、バイナリ ツリーの事前順序走査を実行し、アクセスされた順序でノードの値のリストを返します。

アルゴリズムは次のように機能します。

1. ルート ノードが null の場合は、空のリストを返します。
2. ルート ノードの値を結果リストに追加します。
3. ルートの左側の子で関数を呼び出して、左側のサブツリーを再帰的にトラバースし、返されたリストを結果リストに追加します。
4. ルートの右の子で関数を呼び出して右のサブツリーを再帰的にトラバースし、返されたリストを結果リストに追加します。
5. 結果リストを返します。

このアルゴリズムの時間計算量は O(n) (n はツリー内のノード数)、空間計算量は O(h) (h はツリーの高さ) (コール スタックによる) です。

以下は、反復アプローチを使用した (つまり、再帰を使用しない) ソリューションです。

 fun preorderTraversal(root: TreeNode?): List<Int> { val result = mutableListOf<Int>() val stack = Stack<TreeNode>() var current = root while (current != null || stack.isNotEmpty()) { while (current != null) { result.add(current.val) stack.push(current) current = current.left } current = stack.pop() current = current.right } return result }

この関数は、バイナリ ツリーの事前順序走査を実行し、アクセスされた順序でノードの値のリストを返します。スタックを使用して、まだアクセスする必要があるノードを追跡します。

アルゴリズムは次のように機能します。

1. 空のスタックを初期化し、現在のノードをツリーのルートに設定します。

2. 現在のノードが null でないか、スタックが空でない場合:

   1. 現在のノードが null でない場合:

      1. 現在のノードの値を結果リストに追加します。
      2. 現在のノードをスタックにプッシュします。
      3. 現在のノードをその左の子に設定します。

   2. スタックから最上位ノードをポップし、現在のノードをその右の子に設定します。

3. 結果リストを返します。

このアルゴリズムの時間複雑度は O(n) (n はツリー内のノード数) で、空間複雑度は O(h) (h はツリーの高さ) です。

これが役立つことを願っています！他にご不明な点がございましたら、お問い合わせください。