section4 stack, queue, tree

유효한 괄호쌍

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;
};

Tree 구현

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;
  }
}

이진트리 후위순회(postorder)

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;
};