const isValid = (str) => {
// 최초 입력값이 빈 값이라면 유효하지 않은 괄호쌍으로 간주합니다.
if (str.length === 0) return false; //입력값이 없으면 false반환
// 각각의 여는 괄호에 알맞는 닫는 괄호를 매칭시키기 위한 괄호맵 생성.
const braketsMap = { // 키와 값을 가로값으로 줌
'(': ')',
'[': ']',
'{': '}'
};
const arr = str.split(''); // 문자열을 배열로 변경
const stack = [];
for (let i = 0; i < arr.length; ++i) {
// 1. 여는 괄호 -> stack에 push해야 하는 케이스
if (arr[i] === '(' || arr[i] === '[' || arr[i] === '{') {
stack.push(arr[i]);//왼쪽
} else {
// 2. 닫는 괄호 -> stack에서 pop해야 하는 케이스
// lastElementOfStack 에는 키값이 들어간다
const lastElementOfStack = stack[stack.length - 1];
// braketsMap[]에 키값과 arr[i] 값이 안맞으면 false
if (braketsMap[lastElementOfStack] !== arr[i]) return false;
// 짝이 맞다면 현재 stack의 가장 위에 위치한 괄호를 pop시켜서 stack에서 제거해줌
stack.pop();
}
}
// arr 배열전체를 돌면서 해당 로직을 이행한 후 stack에 어떠한 열린괄호라도 남아있다면 쌍이 맞지 않는 괄호들이 인풋으로 들어왔기 때문에 false를 반환, 그렇지 않고 stack이 비어져 있다면 모든 괄호쌍이 문제없이 유효한 괄호쌍이므로 true를 반환
return stack.length ? false : true;
};
class Tree {
//tree의 constructor를 구현합니다.
//tree의 자식 노드들을 children으로 할당하여 노드의 자식 노드들을 담을 수 있게 설정합니다.
constructor(value) {
this.value = value;
this.children = [];
}
//tree의 자식 노드를 생성 한 후에, 노드의 children에 push해 줍니다.
insertNode(value) {
const childNode = new Tree(value);
// 나오는 형태 (자식으로 추가가 되는 것을 볼 수 있다.
// Tree {
//value: null,
//children: [
// Tree { value: 0, children: [] },
this.children.push(childNode);
}
// tree에서 value값을 탐색합니다.
// 현재 노드의 value 값이 찾는 값과 일치한다면 return합니다.
contains(value) {
if (this.value === value) {
return true;
}
// 노드가 가진 자식 노드를 순회하는 반복문으로 노드의 children 배열을 탐색합니다.
for (let i = 0; i < this.children.length; i += 1) {
const childNode = this.children[i];
if (childNode.contains(value)) {
return true;
}
}
return false;
}
}
const postOrderTraversal = (root) => {
// 출력결과를 저장하기 위한 result 배열을 하나 만들어 줍니다.
let result = [];
// 트리를 재귀적으로 순회하기 위한 재귀함수를 생성합니다.
const dfs = (node) => {
// 재귀의 기저조건으로 방문한 노드가 빈 노드일 경우에 해당 재귀를 종료시킨 후 상위로 올려줍니다.
if (node === null) return;
// 트리를 후위 순회하는 것이기 때문에 node를 root로 보았을 때,
// node 기준으로 왼편 -> 오른편 -> 해당 node 순으로 방문합니다.
dfs(node.left);
dfs(node.right);
result.push(node.val);
}
// 순회 시작을 위해 최초 받은 root노드를 매개변수로 넣어 재귀함수를 실행시켜 주니다.
dfs(root);
// 재귀가 모두 끝난 이후 결과를 반환해 줍니다.
return result;
};