9/25 (월) 이진 트리 전위 순회와 중위 순회 구현하기 TIL

공부한 것

• LeetCode #144. Binary Tree Preorder Traversal

  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/binary-tree-preorder-traversal/description/

  

  전위 순회(Preorder traversal): ‘나’와 두 자식을 기준으로, “나 → 왼 자식 → 오른 자식” 순으로 순회하는 것.

  그렇게 탐색한 순서대로 노드의 값을 담아 숫자 배열로 반환하는 문제였다. 이진 트리가 나올 때마다 하던 데로 손쉽게 풀었다.

• LeetCode #94. Binary Tree Inorder Traversal

  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/binary-tree-inorder-traversal/description/

  

  중위 순회(Inorder traversal): '나'와 나의 두 자식을 기준으로, “왼 자식 -> 나 -> 오른 자식” 순으로 순회하는 것.

  • 생각하는 데 오래 걸렸다. 노드가 8개쯤 있는 임의의 트리를 만들어서 중위 순회를 하면 어떤 순서로 결과가 나와야 하는지를 먼저 적어두고, 그런 결과를 만들어내도록 스택에 넣고 빼는 순서를 역산하며 가설 두 세 가지를 실험한 결과 다음과 같은 해답을 얻을 수 있었다:
  • 내가 푼 해답 코드:

    // iterative solution
    function solution(root: TreeNode): number[] {
    	if (!root) return [];
    
    	// 객체로는 TreeNode객체 타입을 key로 가질 수 없어서(node의 주소값이 문자열로 저장될 줄 알았는데 안된다) 대신 Map을 이용하기로 한다. 
    	const resultMap: Map<TreeNode, number> = new Map();
    	const stack: Array<TreeNode> = [root];
    
    	while (stack.length) {
    		// 1. 
    		const node = stack[stack.length - 1];
    		
    		if (node.left && !resultMap.has(node.left)) {
    			// 2. 만약 지금 보고 있는 노드에 왼쪽 자식이 있고 이 자식이 resultObj에 들어가있지 않다면 지금 노드를 스택에 그대로 두고 왼 자식을 스택에 추가한다.  
    			stack.push(node.left);
    		} else {
    			// 3. 그렇지 않으면
    			// 	  스택에서 뽑고, 지금 노드와 값을 result 맵에 넣고, 오른 자식을 (있다면) 스택에 넣는다. 
    			stack.pop();
    			resultMap.set(node, node.val);
    			node.right && stack.push(node.right);
    		}
    	}
    	
    	return [...resultMap.values()];
    }

배운 것

• ‘왼쪽 자식이 있으면 그 자식을 스택에 추가하기’를 더 간략하게 쓰는 방법을 알게 되었다:

  // 원래 알던 방법: 
  if (node.left) stack.push(node.left);
  
  // 새롭게 알게 된 방법: 
  node.left && stack.push(node.left);

• 이터러블과 이터레이터를 다시 간단히 정리해보았다.

이터러블(Iterable)과 이터레이터(Iterator)

Iterable(이터러블): 반복 가능한 객체. 정확히는 Symbol.iterator() 메소드를 가지고 있는 객체를 말한다.

1) 대표적인 이터러블 객체: Array, String, Map, Set

2) 이터러블을 써야하는 대표적인 문법:

• "for ... of __" 문법에서 __ 자리에.

• Array.from(__)

• 전개구문 중 배열 스프레드(배열 리터럴)에: [...__, ...__,]

1)의 네 가지와 2)의 세 가지를 기억하고 있다면 둘을 얼마든지 조합해서 쓸 수 있다.

// 예시: 
[...resultMap.values()]; // O
Array.from(...resultMap.values()); // X
Array.from(resultMap.values()); // O
Array.from(Object.values(resultObj)); O

Iterator(이터레이터): 이터러블 객체를 순회하면서 값을 하나씩 반환하는 객체. next() 메소드를 가진다.

Uploaded by N2T