[자료구조] 이진트리 후위순회

// 주어진 루트 노드
class TreeNode {
	constructor(val, left, right) {
		this.val = val === undefined ? 0 : val;
		this.left = left === undefined ? null : left;
		this.right = right === undefined ? null : right;
	}
}

// 1. 재귀적 풀이법
const postOrderTraversal = (root) => {
  let result = [];
    
	// 재귀함수
  const dfs = (node) => {
	// 노드가 빈 노드일 경우에 재귀 종료
    if (node === null) return;
    
    // 후위순회니까 왼쪽, 오른쪽, 현재 노드 순으로 방문
    dfs(node.left);
    dfs(node.right);

    result.push(node.val);
  }

	// 재귀함수 호출
  dfs(root);

  return result;
}

// 2. 반복문 풀이법
const postOrderTraversal = (root) => {
  const stack = [];
  const result = [];

  // 루트가 빈 노드일 경우에 결과 리턴
  if (root === null) return result;

  stack.push(root);

  while (stack.length) {
    const node = stack.pop();
	
    // 루트 노드를 출력값에서 뒤로 밀리게끔 결과값에 먼저 넣어준다.
    result.unshift(node.val);

    // 다음 방문을 위한 node의 자식을 stack에 담을 때는 기존 순서대로 left -> right순으로 담아주면 된다.
    node.left && stack.push(node.left);
    node.right && stack.push(node.right);
  }

  return result;
};