9/1 (금) 트리 문제 기초 접근법을 3가지로 정리하다 TIL

공부한 것

• LeetCode #226. Invert Binary 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/invert-binary-tree/description/

  

  트리를 뒤집어 반환하는 문제이다. 각 노드별로 좌우 자식을 바꿔주면 되고 이는 결국 노드를 전부 방문해야 한다는 얘기가 된다. 기초적인 전위 순회(Preorder Traversal)를 해주었고, 이 전위 순회를 구현하는 데 대표적으로 다음과 같은 세 가지 방법을 이용할 수 있다:

  • 1. 재귀 호출을 통한 깊이 우선 탐색(DFS)

    function solution(root: TreeNode): TreeNode {
    
    	// node(현재 레벨의, 타겟 노드)를 각각 어떻게 지정할 것인가
    	// (순회할 것인가)가 문제다. node를 순회할 수만 있으면, 자식들이
    	// null이어도 좌우를 바꾸는 과정에는 문제가 없다. node가 null이 
      // 아닌 동안에만 재귀적으로 호출하면 되겠다. node가 null이면 그냥 
    	// 자기 자신을 반환하도록 하고. node가 null이 아니면 좌우 자식을 
    	// 바꾸고 자기 자신을 반환한다.
    	if (!root) return root;
    
    	let temp: TreeNode;
    	temp = solution(root.right);
    	root.right = solution(root.left);
    	root.left = temp;
    
    	return root;
    }

  • 2. 스택 자료구조를 이용한 깊이 우선 탐색(DFS)

    // 똑같은 DFS이지만 스택을 대신 이용한 순회 방법도 있다: 
    function solution3(root: TreeNode | null): TreeNode | null {
    	if (!root) return root;
    
    	const stack: Array<TreeNode> = [root];
    	while (stack.length) {
    		let node = stack.pop();
    		let temp = node.left;
    		node.left = node.right;
    		node.right = temp;
    
    		if (node.left) stack.push(node.left);
    		if (node.right) stack.push(node.right);
    	}
    
    	return root;
    }

  • 3. 큐 자료구조를 이용한 너비 우선 탐색(BFS)

    // solution1과 같은 재귀 호출 방법은, 콜 스택이 overflow 되기 
    // 십상이므로 더 robust한 방법을 찾아야 한다: Queue 자료구조를
    // 이용한 BFS 방식으로 순회함. 각 노드를 (위에서부터)딱 한 번
    // 씩만 방문하므로, 너비 우선 탐색(BFS)도 유효한 순회 방법이다.
    function solution2(root: TreeNode | null): TreeNode | null {
    	if (!root) return root;
    
    	const queue: Array<TreeNode> = [root];
    	while (queue.length) {
    		let node = queue.shift();
    		let temp = node.left;
    		node.left = node.right;
    		node.right = temp;
    
    		if (node.left) queue.push(node.left);
    		if (node.right) queue.push(node.right);
    	} 
    
    	return root;
    }

  세 가지 모두로 풀어보았다.

Tree 자료구조 문제 모음 (협조: ChatGPT)

• 실무에 가깝게 사용하는 방법

  전체 리스트 : https://leetcode.com/list?selectedList=r6sbbwoh

  https://leetcode.com/list?selectedList=r6sbbwoh

  1. Serialize and Deserialize Binary Tree - 문제 번호: 297 이진 트리를 직렬화하고 역직렬화하는 문제로, 트리를 데이터 형태로 저장하고 복원하는 실무적인 상황을 모방합니다.

  2. Find Duplicate Subtrees - 문제 번호: 652 중복 서브트리를 찾는 문제로, 서브트리들의 중복을 찾아내는 실무에서도 유용한 상황을 연습할 수 있습니다.

  3. Most Frequent Subtree Sum - 문제 번호: 508 서브트리 합의 가장 빈번한 값들을 찾는 문제로, 트리의 서브트리 합을 다루는 실무 상황을 반영합니다.

  4. Lowest Common Ancestor of a Binary Tree II - 문제 번호: 1676 236 이진 트리에서 두 노드의 가장 낮은 공통 조상을 찾는 문제로, 노드들이 두 번 등장하는 상황을 다룹니다.

  5. Binary Tree Right Side View - 문제 번호: 199 이진 트리의 오른쪽 뷰를 찾는 문제로, 실무에서 트리의 구조를 시각화하여 확인하는 상황을 연습합니다.

  6. Count Complete Tree Nodes - 문제 번호: 222 완전 이진 트리의 노드 개수를 세는 문제로, 트리의 노드 개수를 효율적으로 세는 상황을 모방합니다.

  7. Path Sum III - 문제 번호: 437 이진 트리에서 특정 합을 가지는 경로의 개수를 찾는 문제로, 트리의 경로 합을 찾아내는 상황을 연습합니다.

  8. All Nodes Distance K in Binary Tree - 문제 번호: 863 이진 트리에서 특정 거리만큼 떨어진 노드들을 찾는 문제로, 트리의 거리 기반 탐색을 실습할 수 있습니다.

  9. Binary Tree Cameras - 문제 번호: 968 이진 트리의 카메라 설치를 최소화하여 모든 노드를 감시하는 문제로, 실무에서 리소스를 최적화하여 모든 상황을 감시하는 상황을 나타냅니다.

  10. Binary Tree Maximum Depth - 문제 번호: 104 이진 트리의 최대 깊이를 찾는 문제로, 트리의 깊이를 파악하는 상황을 연습합니다.

  11. Binary Tree Level Order Traversal II - 문제 번호: 107 이진 트리의 레벨 순서대로 노드 값을 반환하는 문제로, 트리의 레벨 순서대로 값을 추출하는 상황을 연습합니다.

  12. Binary Tree Zigzag Level Order Traversal - 문제 번호: 103 이진 트리의 레벨 순서대로 노드 값을 번갈아가며 반환하는 문제로, 트리의 값들을 번갈아가며 탐색하는 상황을 연습합니다.

  13. Maximum Depth of N-ary Tree - 문제 번호: 559 N-ary 트리의 최대 깊이를 찾는 문제로, 다른 종류의 트리 자료구조에서도 깊이를 계산하는 상황을 연습합니다.

  14. Second Minimum Node In a Binary Tree - 문제 번호: 671 이진 트리에서 두 번째로 작은 값을 찾는 문제로, 트리 내에서 두 번째로 작은 값을 탐색하는 상황을 연습합니다.

• 전위, 중위, 후위 순회를 활용하는 문제들

  전체 리스트: https://leetcode.com/list?selectedList=r6syzu05

  다음에 소개된 문제들 중 프리미엄 문제는 위의 리스트에 포함되어 있지 않다.

  전위 순회 활용 예 1: 표현식 계산

  1. LeetCode 문제: Evaluate Reverse Polish Notation
     • 문제 설명: 주어진 역폴란드 표기식을 계산하는 문제입니다.
     • 전위 순회 적용: 표현식을 트리로 나타내고 전위 순회를 통해 연산자를 먼저 처리하고 피연산자를 계산합니다.

  2. LeetCode 문제: Construct Binary Expression Tree from String
     • 문제 설명: 주어진 문자열로부터 이진 표현식 트리를 구성하는 문제입니다.
     • 전위 순회 적용: 주어진 문자열을 트리로 나타내고 전위 순회를 통해 트리를 구성합니다.

  전위 순회 활용 예 2: 복제 및 클로닝

  1. LeetCode 문제: Clone Binary Tree With Random Pointer
     • 문제 설명: 무작위 포인터를 가진 이진 트리를 복제하는 문제입니다.
     • 전위 순회 적용: 원본 트리의 구조를 전위 순회하면서 새로운 노드를 생성하여 클로닝합니다.

  2. LeetCode 문제: Find a Corresponding Node of a Binary Tree in a Clone of That Tree
     • 문제 설명: 두 개의 동일한 구조를 가진 이진 트리에서 원본 트리의 노드와 클론 트리의 노드를 대응시키는 문제입니다.
     • 전위 순회 적용: 원본 트리와 클론 트리를 동시에 전위 순회하면서 대응되는 노드를 찾습니다.

  전위 순회 활용 예 3: 폴더 및 파일 구조 순회

  1. Find Duplicate File in System: 파일 시스템에서 중복된 파일을 찾는 문제로, 파일 경로를 트리로 표현하고 전위 순회를 활용해 파일을 처리합니다.

  2. Delete Node in a BST: 이진 검색 트리에서 노드를 삭제하는 문제로, 전위 순회를 활용해 삭제할 노드를 찾고 처리합니다.

  중위 순회 활용 예 1: 정렬된 데이터의 표현

  1. LeetCode 문제: Convert Sorted List to Binary Search Tree
     • 문제 설명: 정렬된 연결 리스트를 이진 검색 트리로 변환하는 문제입니다.
     • 전위 순회 적용: 중간 노드를 루트로 선택하고 왼쪽 서브리스트와 오른쪽 서브리스트를 중위 순회 방식으로 트리에 추가합니다.

  2. LeetCode 문제: Increasing Order Search Tree
     • 문제 설명: 이진 검색 트리를 중위 순회 결과가 증가하는 순서로 재조정하는 문제입니다.
     • 전위 순회 적용: 중위 순회를 하면서 노드를 방문하고 순서대로 새로운 트리를 만들어나갑니다.

  중위 순회 활용 예 2: 검색 연산

  1. LeetCode 문제: Kth Smallest Element in a BST
     • 문제 설명: 이진 검색 트리에서 k번째로 작은 원소를 찾는 문제입니다.
     • 전위 순회 적용: 중위 순회를 하면서 순서대로 k번째 노드를 찾아 반환합니다.

  2. LeetCode 문제: Validate Binary Search Tree
     • 문제 설명: 주어진 이진 트리가 이진 검색 트리인지 여부를 확인하는 문제입니다.
     • 전위 순회 적용: 중위 순회를 하면서 각 노드의 값이 이전 노드의 값보다 큰지 확인하며 검증합니다.

  중위 순회 활용 예 3: 수식 트리에서 중위 표기식 생성

  1. Construct Binary Tree from String: 주어진 문자열을 이용하여 이진 트리를 구성하는 문제로, 중위 순회를 활용하여 중위 표기식을 생성합니다.

  2. Expression Tree Build: 주어진 후위 표기식을 이용하여 표현식 트리를 구성하는 문제로, 중위 순회를 활용하여 중위 표기식을 생성합니다.

  후위 순회 활용 예 1: 메모리 해제

  1. LeetCode 문제: Delete Nodes And Return Forest
     • 문제 설명: 이진 트리에서 주어진 노드들을 삭제하고 남은 서브트리들을 반환하는 문제입니다.
     • 전위 순회 적용: 후위 순회를 하면서 삭제해야 할 노드를 찾고 해당 노드를 삭제한 뒤 남은 서브트리들을 반환합니다.

  2. LeetCode 문제: Binary Tree Pruning
     • 문제 설명: 이진 트리에서 0이 아닌 노드를 모두 유지하고 0인 노드를 삭제하는 문제입니다.
     • 전위 순회 적용: 후위 순회를 하면서 0인 노드를 삭제하고 해당 노드의 부모 노드의 자식 포인터를 갱신합니다.

  3. Delete Leaves With a Given Value: 주어진 트리에서 특정 값을 가진 리프 노드를 삭제하는 문제로, 후위 순회를 활용하여 리프 노드부터 삭제합니다.

  후위 순회 활용 예 2: 수식 트리 계산

  1. LeetCode 문제: Binary Tree Maximum Path Sum
     • 문제 설명: 이진 트리의 노드들을 거쳐서 얻을 수 있는 최대 경로 합을 계산하는 문제입니다.
     • 전위 순회 적용: 후위 순회를 하면서 현재 노드를 거쳐서 얻을 수 있는 최대 경로 합을 갱신합니다.

  2. LeetCode 문제: House Robber III
     • 문제 설명: 이진 트리의 각 노드에는 훔칠 수 있는 돈의 양이 주어질 때, 서로 인접하지 않은 노드들의 돈의 최대 합을 계산하는 문제입니다.
     • 전위 순회 적용: 후위 순회를 하면서 각 노드를 방문하면서 노드를 훔칠 때와 훔치지 않을 때의 경우를 비교하여 최대 합을 계산합니다.

  3. Evaluate Expression: 주어진 수식을 후위 표기식으로 표현하고, 후위 순회를 활용하여 연산을 수행합니다.

  4. Evaluate Reverse Polish Notation: 후위 표기식을 계산하기 위해 스택과 후위 순회를 사용하여 피연산자와 연산자를 처리합니다.

Uploaded by N2T