8/31 (목) 트리 순회 3형제는 깊이 우선 탐색(DFS)의 일종이다 TIL

공부한 것

• LeetCode #572. Subtree of Another Tree

  LeetCode - The World's Leading Online Programming Learning Platform

  Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

  https://leetcode.com/problems/subtree-of-another-tree/description/

  

  처음 생각해낸 방법이 대부분의 사람들이 채택한 로직임을 알게 되어서 뿌듯했다.

DFS와 BFS에 대하여

: 트리나 그래프와 같은 자료구조에서 노드를 탐색하는 방법이다.

DFS: Depth-First Search(깊이 우선 탐색)

- 한 경로를 끝까지 탐색

- 스택 또는 재귀함수로 구현

- 전위, 중위, 후위 트리 순회 모두가 다 DFS의 일종임.

• 재귀 호출을 이용한 DFS 구현 예시:

  // 시간복잡도: 각 노드마다 isSameTree 함수를 한 번씩 호출하므로...
  // 공간복잡도: 재귀 호출의 경우 호출 스택에 저장되는 공간이 추가로 필요하게 되므로... 
  // Time complexity: O(N*S) (N: root length, S: subRoot length)
  // Space complexity: O(H) (H: height of root)
  function solution2(root: TreeNode | null, subRoot: TreeNode | null): boolean {
  	if (!root) return false;
  
  	if (isSameTree(root, subRoot)) return true;
  
  	return solution2(root.left, subRoot) || solution2(root.right, subRoot);
  }
  // solution2의 보조함수
  function isSameTree(root: TreeNode | null, subRoot: TreeNode | null): boolean {
  	if (!root && !subRoot) return true;
  	if (!root || !subRoot) return false;
  	if (root.val !== subRoot.val) return false;
  
  	return isSameTree(root.left, subRoot.left) && isSameTree(root.right, subRoot.right);
  }

• 스택을 이용한 DFS 구현 예시:

  // 다른 해답: solution1과 로직은 같되 root을 탐색할 때 스택을 이용하여 DFS 순회
  function solution3(root: TreeNode | null, subRoot: TreeNode | null): boolean {
  	if (!root) return false;
  
  	const stack = [root];
  
  	while (stack.length > 0) {
  		const node = stack.pop(); // stack이므로 pop. 
  
  		if (node) {
  			if (isSameTree(node, subRoot)) return true;
  			stack.push(node.left);
  			stack.push(node.right);
  		}
  	}
  
  	return false;
  }
  
  function isSameTree(root: TreeNode | null, subRoot: TreeNode | null): boolean {
  	if (!root && !subRoot) return true;
  	if (!root || !subRoot) return false;
  	if (root.val !== subRoot.val) return false;
  
  	return isSameTree(root.left, subRoot.left) && isSameTree(root.right, subRoot.right);
  }

BFS: Breadth-First Search(너비 우선 탐색)

- 각 레벨별로 노드들을 탐색

- 큐를 이용하여 구현

- 가까운 노드부터 탐색하므로 최단 경로를 찾는데 유용함.

• 큐를 이용한 BFS 구현 예시:

  function solution4(root: TreeNode | null, subRoot: TreeNode | null): boolean {
  	if (!root && !subRoot) return true;
  	if (!root || !subRoot) return false;
  
  	console.log(root.printTreeLevels().join('\n'), '\n', JSON.stringify(root));
  	let queue = [root];
  	while (queue.length) {
  		let node = queue.shift();
  
  		if (JSON.stringify(node) === JSON.stringify(subRoot)) return true;
  
  		if (node?.left) queue.push(node.left);
  		if (node?.right) queue.push(node.right);
  	}
  
  	return false;
  }

트리 순회 방식

Preorder Traversal(전위 순회):

- 현재 노드, 왼쪽 자식, 오른쪽 자식 노드 순서로 순회

- 트리 구조를 복원하거나 복제하는데 사용

Inorder Traversal(중위 순회):

- 왼쪽 자식, 현재 노드, 오른쪽 자식 노드 순서로 순회

- 이진 탐색 트리에서 노드 값을 오름차순으로 정렬된 리스트로 얻을 때 사용하면 유용함

Postorder Traversal(후위 순회):

- 왼쪽 자식, 오른쪽 자식, 현재 노드 순서로 순회

- 후위 표현식 계산에 사용됨

Uploaded by N2T