// 例1: 二分木の深さ優先探索
// スタック版（反復）
function dfsIterative(root) {
if (!root) return [];
let result = [];
let stack = [root];
while (stack.length > 0) {
let node = stack.pop();
result.push(node.val);
// 右の子を先にプッシュ（左の子を先に処理するため）
if (node.right) stack.push(node.right);
if (node.left) stack.push(node.left);
}
return result;
}
// 再帰版
function dfsRecursive(root, result = []) {
// 基本ケース
if (!root) return result;
// 現在のノードを処理
result.push(root.val);
// 再帰呼び出し（左、右の順）
dfsRecursive(root.left, result);
dfsRecursive(root.right, result);
return result;
}
// 例2: 階乗計算
// スタック版（反復）
function factorialIterative(n) {
if (n <= 1) return 1;
let stack = [];
let current = n;
// スタックに値をプッシュ
while (current > 1) {
stack.push(current);
current--;
}
let result = 1;
// スタックから値をポップして計算
while (stack.length > 0) {
result *= stack.pop();
}
return result;
}
// 再帰版
function factorialRecursive(n) {
// 基本ケース
if (n <= 1) return 1;
// 再帰呼び出し
return n * factorialRecursive(n - 1);
}
// 例3: 括弧の妥当性チェック
// スタック版（反復）
function isValidParenthesesIterative(s) {
let stack = [];
let mapping = {')': '(', '}': '{', ']': '['};
for (let char of s) {
if (char in mapping) {
// 閉じ括弧の場合
if (stack.length === 0 || stack.pop() !== mapping[char]) {
return false;
}
} else {
// 開き括弧の場合
stack.push(char);
}
}
return stack.length === 0;
}
// 再帰版
function isValidParenthesesRecursive(s, index = 0, stack = []) {
// 基本ケース：文字列の終端
if (index === s.length) {
return stack.length === 0;
}
let char = s[index];
let mapping = {')': '(', '}': '{', ']': '['};
if (char in mapping) {
// 閉じ括弧の場合
if (stack.length === 0 || stack[stack.length - 1] !== mapping[char]) {
return false;
}
// スタックからポップ（新しい配列を作成）
let newStack = stack.slice(0, -1);
return isValidParenthesesRecursive(s, index + 1, newStack);
} else {
// 開き括弧の場合：スタックにプッシュ
let newStack = [...stack, char];
return isValidParenthesesRecursive(s, index + 1, newStack);
}
}
// 例4: 文字列の逆順
// スタック版（反復）
function reverseStringIterative(str) {
let stack = [];
// 文字をスタックにプッシュ
for (let char of str) {
stack.push(char);
}
let result = '';
// スタックからポップして結果を構築
while (stack.length > 0) {
result += stack.pop();
}
return result;
}
// 再帰版
function reverseStringRecursive(str, index = 0) {
// 基本ケース：文字列の終端
if (index === str.length) {
return '';
}
// 再帰呼び出しの結果の後に現在の文字を追加
return reverseStringRecursive(str, index + 1) + str[index];
}
// テスト用のサンプルデータ
console.log("=== 深さ優先探索のテスト ===");
// 二分木のノード構造（簡単なテスト用）
const tree = {
val: 1,
left: {
val: 2,
left: { val: 4, left: null, right: null },
right: { val: 5, left: null, right: null }
},
right: {
val: 3,
left: { val: 6, left: null, right: null },
right: { val: 7, left: null, right: null }
}
};
console.log("反復版DFS:", dfsIterative(tree));
console.log("再帰版DFS:", dfsRecursive(tree));
console.log("\n=== 階乗計算のテスト ===");
console.log("反復版階乗(5):", factorialIterative(5));
console.log("再帰版階乗(5):", factorialRecursive(5));
console.log("\n=== 括弧妥当性チェックのテスト ===");
console.log("反復版括弧チェック:", isValidParenthesesIterative("({[]})"));
console.log("再帰版括弧チェック:", isValidParenthesesRecursive("({[]})"));
console.log("\n=== 文字列逆順のテスト ===");
console.log("反復版逆順:", reverseStringIterative("hello"));
console.log("再帰版逆順:", reverseStringRecursive("hello"));