8/28 (월) 너비 우선 탐색(BFS)과 새로운 메소드 TIL

공부한 것

LeetCode #100. Same 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/same-tree/
Tree 카테고리로 넘어왔다. 기본적으로 재귀 호출이 필요한 구조인 듯 하다.

LeetCode #110. Balanced Binary Tree

케이스 하나가 막혀서 하루 종일 고민해봤지만 아직 못 풀어냈다. TreeNode 클래스에 현재 노드 이하 트리를 전부 그려서 출력하는 printTreLevels() 메소드를 작성해넣었는데 조악하게나마 잘 작동한다. 이 메소드를 만드는 동안 BFS(너비 우선 탐색)의 코드 구조를 익혀서 문제풀이에 활용할 수 있었다.

코드와 출력 결과는 대략 다음과 같다:

/**
 * Definition for a binary tree node.
*/
class TreeNode {
    val: number
    left: TreeNode | null
    right: TreeNode | null
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = (val===undefined ? 0 : val)
        this.left = (left===undefined ? null : left)
        this.right = (right===undefined ? null : right)
	}

	printTreeLevels(node: TreeNode | null = this): string[] {
		const result: string[] = [];
		if (node === null) {
			return result;
		}

		// [각 노드, 노드가 위치한 레벨, 각 노드의 부모 노드]
		const queue: Array<[TreeNode, number, TreeNode]> = [[node, 0, null]];
		let currentLevel = 0; 
		let currentLevelString = '';
		let connectorLine = '';

		while (queue.length > 0) {	
			const [currentNode, level, parentNode] = queue.shift()!; // '!': non-null assertion operator. TypeScript에게 해당 값이 항상 존재한다고 알려줌. shift()의 결과가 undefined이더라도 TypeScript의 strict 모드 경고를 발생시키지 않도록 한다.

			// '지금' 레벨에서 출력해야 하는(=같은 레벨의) 노드가 아니면, result 배열에 현재까지 만든 string을 넣고 string을 초기화한다. 
			if (level !== currentLevel) {
				result.push(currentLevelString);
				result.push(connectorLine);
				currentLevelString = '';
				connectorLine = '';
				currentLevel = level;
			}

			// 현재 레벨의 자식 레벨에 이어지는 '연결 라인' 생성
			// ex) connectorLine = '/\ /\ /\ /\'
			let connector = '';
			if (currentNode.left) {
				connector += `/`;
				if (currentNode.right) {
					connector += '\\ ';
				} else connector += '  ';
			} else if (currentNode.right) {
				connector += ' \\ ';
			} else connector = '  ';
			connectorLine += connector;

			// 현재 레벨의 노드를 나열한 '노드 라인' 생성
			// ex) currentLevelString = '8 9 10 11 12 13 14 15'
			if (!parentNode) currentLevelString += `${currentNode.val}`;
			else if (currentNode && currentNode === parentNode.left) { // 현재 노드가 '왼 자식'
				currentLevelString += `${currentNode.val} `;
			} else if (currentNode) { // 현재 노드가 '오른 자식'
				if (!parentNode.left) {
					currentLevelString += `  `;
				}
				currentLevelString += `${currentNode.val} `;
			} else { // 현재 노드가 null인 가상의 자식. 근데 적용이 안 되는 것 같다.
				currentLevelString += '       ';
			}

			// 현재 노드에 왼쪽 자식 노드가 있으면 queue(의 끝)에 추가
			if (currentNode.left) {
				queue.push([currentNode.left, level + 1, currentNode]);
			}
			// 현재 노드에 오른쪽 자식 노드가 있으면 queue에 추가
			if (currentNode.right) {
				queue.push([currentNode.right, level + 1, currentNode]);
			}
		}

		// 마지막 노드 처리: 현재까지 만들고 있는 string이 빈 문자열 ''이 아니라면 마지막으로 result 배열에 추가해줌. 
		if (currentLevelString) {
			result.push(currentLevelString);
			result.push(connectorLine);
		}

		return result;
	}
}

// 호출: 
let root = new TreeNode(1);
console.log(root.printTreeLevels().join('\n');

결과:

배운 것

Tree 자료구조의 너비우선 탐색(BFS)의 코드 구조는 대략 다음과 같다:

// BFS 탐색
// 1) queue.shift()로 currentNode를 뽑아와 할 거 다 한 다음에
// 2) .left가 있으면 queue에 넣는다.
// 3) .right이 있으면 queue에 넣는다. 
// 4) queue에 남은 노드가 없어지기까지 계속한다.

Jest 라이브러리에 test.each()라는 메소드가 있어서 그동안 내가 forEach를 활용하던 작성 방식을 거의 있는 그대로 대체할 수 있을 것 같다.
- test.each(data)(name, fn) :
  - data: 반복할 데이터 세트. 배열로 줘야 하고, 각 데이터는 'name' 문자열과 'fn' 함수의 파라미터로 각각 전달된다.
  - name: 각 데이터 세트에 대한 테스트 케이스의 이름을 나타내는 문자열. data 배열에서 각 요소 값을 '%p'같은 플레이스홀더에 하나씩 전달받는다.
  - fn: 실제 테스트 로직을 담은 함수. data 배열에서 전달받은 각 요소 값을 매개변수로 전달받는다.
  플레이스홀더(placeholder): 변수의 이름을 동적으로 생성하는 데 사용되는 문법. %기호 다음에 붙는 문자가 특정 값으로 대체된다. test.each()와 플레이스홀더를 이용해 테스트 케이스의 이름을 동적으로 생성하는 기존의 [].forEach(({tree1, tree2, answer}) => { it(...) }) 방법을 대신할 수 있겠다!
```
// 예시:
test.each([
	[1, 1, 2],
	[1, 2, 3],
])(
	'test.each()와 플레이스홀더 예시 테스트: Adding %i and %i equals %p',
	(a, b, expected) => {
		expect(a + b).toBe(expected);
	}
);

// 테스트 결과: 
√ test.each()와 플레이스홀더 예시 테스트: Adding 1 and 1 equals 2
√ test.each()와 플레이스홀더 예시 테스트: Adding 1 and 2 equals 3
```

Array.from() 메소드에 대하여:
- Array.from(arrayLike, mapFn?, thisArg?)
  - arrayLike: 배열 형태로 변환하려는 유사 배열 객체 혹은 이터러블 객체. 'length' 프로퍼티만 가지는 유사 배열 객체 { length: 5 }를 배열로 변환하였다.
  - mapFn: 배열의 각 요소를 변형하기 위한 매핑 함수. '_' 파라미터는 unknown이라고 하며 사용할 수 없는 값이다... 'index'에 0부터 4까지의 값이 전달되고, 결과적으로 [1,2,3,4,5]와 같이 생긴 배열이 생성된다.
```
it.each(Array.from({ length: 5 }, (_, index) => index + 1))(
	`Both trees with %p nodes are the same`, (numNodes) => {
		tree1 = generateCompleteTree(numNodes);
		tree2 = generateCompleteTree(numNodes);
		expect(solution(tree1, tree2)).toBe(true);
	}
);

// 테스트 결과: 
√ Both trees with 1 nodes are the same (122 ms)
√ Both trees with 2 nodes are the same (4 ms)
√ Both trees with 3 nodes are the same (2 ms)
√ Both trees with 4 nodes are the same (3 ms)
√ Both trees with 5 nodes are the same (3 ms)
```

Uploaded by N2T

공부한 것

배운 것

티스토리툴바