この投稿は、バイナリ ツリーの事前順序トラバーサル、つまり現在のノードがその子の前にアクセスされるツリーをトラバースする方法に関するものです。事前順序トラバーサル アルゴリズムは、最初にルート ノードにアクセスし、次に再帰的に左のサブツリーにアクセスし、次に右のサブツリーにアクセスします。 preorder traversal の結果は、訪問された順序でのノードの値のリストです。この投稿は、バイナリ ツリーをトラバースする方法と、それをさまざまな方法で実装する方法を理解するのに役立ちます。 Preorder traversal は、現在のノードがその子の前にアクセスされる二分木を走査する方法です。このアルゴリズムは、最初にルート ノードにアクセスし、次に左のサブツリーに再帰的にアクセスし、次に右のサブツリーにアクセスします。 preorder traversal の結果は、訪問された順序でのノードの値のリストです。 この問題では、Kotlin の クラスで表されるバイナリ ツリーのルートが与えられます。これには、ノードの値の プロパティと、その左と右の子のそれぞれの と プロパティがあります。あなたの仕事は、バイナリ ツリーの事前順序トラバーサルを実行し、ノードの値のリストを返す関数の 2 つの実装を記述することです。 1 つは再帰的なソリューションであるべきで、もう 1 つは再帰を使用すべきではありません。 TreeNode val left right 関数のクラス シグネチャは次のとおりです。 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 } この関数は、バイナリ ツリーの事前順序走査を実行し、アクセスされた順序でノードの値のリストを返します。 アルゴリズムは次のように機能します。 ルート ノードが null の場合は、空のリストを返します。 ルート ノードの値を結果リストに追加します。 ルートの左側の子で関数を呼び出して、左側のサブツリーを再帰的にトラバースし、返されたリストを結果リストに追加します。 ルートの右の子で関数を呼び出して右のサブツリーを再帰的にトラバースし、返されたリストを結果リストに追加します。 結果リストを返します。 このアルゴリズムの時間計算量は 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 } この関数は、バイナリ ツリーの事前順序走査を実行し、アクセスされた順序でノードの値のリストを返します。スタックを使用して、まだアクセスする必要があるノードを追跡します。 アルゴリズムは次のように機能します。 空のスタックを初期化し、現在のノードをツリーのルートに設定します。 現在のノードが null でないか、スタックが空でない場合: 現在のノードが null でない場合: 現在のノードの値を結果リストに追加します。 現在のノードをスタックにプッシュします。 現在のノードをその左の子に設定します。 スタックから最上位ノードをポップし、現在のノードをその右の子に設定します。 結果リストを返します。 このアルゴリズムの時間複雑度は O(n) (n はツリー内のノード数) で、空間複雑度は O(h) (h はツリーの高さ) です。 これが役立つことを願っています！他にご不明な点がございましたら、お問い合わせください。
