참고자료
https://blog.bitsrc.io/depth-first-search-of-a-binary-tree-in-javascript-874701d8210a

https://intrepidgeeks.com/tutorial/dfs-bfs-and-js-implementation

• Binary search tree representation of [27, 14, 35, 10, 19, 31, 42]
  

• 순환 순서
  Pre-order: parent → left child → right child
  In-order: left child → parent → right child
  Post-order: left child → right child → parent

앞에 접두사는 언제 부모 노드가 방문되었냐를 알려준다

Pre-order: [27, 14, 10, 19, 35, 31, 42]
In-order: [10, 14, 19, 27, 31, 35, 42]
Post-order: [10, 19, 14, 31, 42, 35, 27]

In-order 순회는 타고 올라가는 순서로 보이기 때문에 특별해 보인다.
사실은 만약 이진트리에서 In-order 가 ascending이 아니라면 그 트리는 정의 상으로 BST가 아니다.

이 구조를 사용한 문제 유형에는
1. 경로 탐색 유형 (최단 거리/시간)
2. 네트워크 유형 (연결)
3. 조합 유형 (모든 조합 만들기)
https://codesyun.tistory.com/79

---

리트코드 DFS 풀이

리트코드 https://leetcode.com/problems/binary-tree-pruning/ 풀이

function TreeNode(val, left, right) {
  this.val = val === undefined ? 0 : val;
  this.left = left === undefined ? null : left;
  this.right = right === undefined ? null : right;
}

const root = new TreeNode(1); // 0
root.left = new TreeNode(0); // 1
root.right = new TreeNode(1); // 1
root.left.left = new TreeNode(0); // 2
root.left.right = new TreeNode(0); // 2
root.right.left = new TreeNode(0); // 2
root.right.right = new TreeNode(1); // 2

const pruneTree = (root) => {
  if (root.left) root.left = pruneTree(root.left); // 1
  if (root.right) root.right = pruneTree(root.right); // 2
  if (!root.left && !root.right && root.val === 0) return null; // 3
  return root;
};

// 깊이 1 탐색 ->
console.log(pruneTree(root));

재귀 사용...

---

프로그래머스 타겟 넘버

주어진 모든 숫자에 (+)연산과 (-)연산을 하는 경우를 탐색해 타겟 숫자가 나오는 횟수를 카운트하면 된다.
시간 복잡도는 O(2^n)
BFS는 큐로 구현하고 DFS는 재귀함수

DFS 알고리즘을 이용하면 전체 숫자가 (+) (-)일 모든 경우의 수를 탐색할 수 있다.

재귀 함수 -> 참고 사이트
반복과 재귀 : DFS 문제를 재귀로 구현하면 편리한 이유

function solution(numbers, target) {
  return dfs(0, 0, 0, numbers, target);
}

const dfs = (count, sum, answerCount, numbers, target) => {
  if (count === numbers.length && sum === target) {
    return ++answerCount;
  } else if (count !== numbers.length) {
    return (
      dfs(count + 1, sum + numbers[count], answerCount, numbers, target) +
      dfs(count + 1, sum - numbers[count], answerCount, numbers, target)
    );
  }
  return answerCount;
};

리턴값이 두개가 들어가서 헷갈렸는데 저게 타고타고가서 결국엔 조건에 맞는 노드마다 answerCount에 ++ 하고 리턴함 (++answerCount) -> 그리고 그걸 또 더한걸 리턴함 -> 그래서 총 answerCount값이 나옴..!!

와.. 한참 헤맸다

대박 쩐다
금방 이해할 줄 알았는데 .. 역시 나는 정말 .. 말하는 감자다

---

하루 마무리

• 완료한 것 ❌🔺✅
  익스프레스 미들웨어 만들기 ❌
  DFS 자료구조 & 알고리즘 문제 풀기 ✅
  코어자바스크립트 챕터 6 복습 ❌
  코어자바스크립트 챕터 7 공부 ❌
  네트워크 스터디 ✅
  네트워크 공부 (ip계층) ❌

• 하루 반성
  상담 일정이 있어서 갔다오느라 시간 허비를 많이 했다.
  DFS 알고리즘, 재귀함수가 너무 낯설고 어려워서 너무 많이 헤매느라 시간 허비 많이했다.
  목표를 별로 달성하지 못했다.....

• 피드백
  상담 그만 뒀음
  내일은 알고리즘 대신 구현을 중심으로 해야겠다.

• 내일 할 것
  DFS 자료구조 & 알고리즘 문제 복습
  코어자바스크립트 챕터 7 공부
  네트워크 공부 (ip계층)
  익스프레스 미들웨어 만들기

---