공통트리트라이class Node { constructor(value) { this.value = value; this.left = null; this.right = null; } } class Tree { constructor(node) { this.root = node; } preorder() { const answer = []; const stack = [this.root]; while (stack.length > 0) { const currentNode = stack.pop(); answer.push(currentNode.value); if (currentNode.right) stack.push(currentNode.right); if (currentNode.left) stack.push(currentNode.left); } return answer; } inorder() { const answer = []; const stack = []; let currentNode = this.root; while (true) { while (currentNode) { stack.push(currentNode); currentNode = currentNode.left; } if (stack.length > 0) { currentNode = stack.pop(); answer.push(currentNode.value); currentNode = currentNode.right; } else { break; } } return answer; } postorder() { const answer = []; const stack = []; let currentNode = this.root; while (true) { while (currentNode) { if (currentNode.right) stack.push(currentNode.right); stack.push(currentNode); currentNode = currentNode.left; } if (stack.length > 0) { currentNode = stack.pop(); if (currentNode.right && stack[stack.length - 1] === currentNode.right) { stack.pop(); stack.push(currentNode); currentNode = currentNode.right; } else { answer.push(currentNode.value); currentNode = null; } } else { break; } } return answer; } } const tree = new Tree(new Node(9)); tree.root.left = new Node(3); tree.root.right = new Node(8); tree.root.left.left = new Node(2); tree.root.left.right = new Node(5); tree.root.right.right = new Node(7); tree.root.left.right.right = new Node(4); console.log(tree.preorder()); console.log(tree.inorder()); console.log(tree.postorder());
class Node { constructor(value) { this.value = value; this.left = null; this.right = null; } } class Tree { constructor(node) { this.root = node; } preorder(currentNode) { console.log(currentNode.value); if (currentNode.left) this.preorder(currentNode.left); if (currentNode.right) this.preorder(currentNode.right); } inorder(currentNode) { if (currentNode.left) this.inorder(currentNode.left); console.log(currentNode.value); if (currentNode.right) this.inorder(currentNode.right); } postorder(currentNode) { if (currentNode.left) this.postorder(currentNode.left); if (currentNode.right) this.postorder(currentNode.right); console.log(currentNode.value); } } const tree = new Tree(new Node(9)); tree.root.left = new Node(3); tree.root.right = new Node(8); tree.root.left.left = new Node(2); tree.root.left.right = new Node(5); tree.root.right.right = new Node(7); tree.root.left.right.right = new Node(4); tree.preorder(tree.root); tree.inorder(tree.root); tree.postorder(tree.root);
class Node { constructor(value = '') { this.value = value; this.children = new Map(); } } class Trie { constructor() { this.root = new Node(); } insert(string) { let currentNode = this.root; for (const char of string) { if (!currentNode.children.has(char)) { currentNode.children.set(char, new Node(currentNode.value + char)); } currentNode = currentNode.children.get(char); } } has(string) { let currentNode = this.root; for (const char of string) { if (!currentNode.children.has(char)) { return false; } currentNode = currentNode.children.get(char); } return true; } autocomplete(string) { if (string === '') { return []; } let targetNode = this.root; for (const char of string) { targetNode = targetNode.children.get(char); } const answer = []; const stack = [targetNode]; // DFS가 아닌 BFS로 해결해도 상관없다. while (stack.length > 0) { const currentNode = stack.pop(); if (currentNode.children.size > 0) { for (const [_, node] of currentNode.children) { stack.push(node); } } else { answer.push(currentNode.value); } } return answer; } } const trie = new Trie(); trie.insert('cat'); trie.insert('can'); trie.insert('cap'); trie.insert('code'); trie.insert('coworker'); trie.insert('cookie'); console.log(trie.autocomplete('co')); // ['cookie', 'coworker', 'code']