8/30 (수) 깊이 우선 탐색(DFS) 예제 코드TIL

공부한 것

• LeetCode #110. Balanced 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/balanced-binary-tree/description/

  

  이상한 테스트 케이스 하나가 있는 것으로 결론 내리고 마무리 지었다.

배운 것

• 깊이 우선 탐색(DFS)에 해당하는 예제와 생각 과정은 다음과 같다:
  • 로직:

    1) 현재 노드가 null이면 0을 반환하고,

    2) 현재 노드의 두 '자식 노드'에 대한 재귀호출로 현재 잎 노드부터 자식 노드까지의 판단을 불러온다.

    2-1) 결과가 어차피 -1이었으면 바로 -1을 반환해주도록 한다. '현재 노드'에 대한 판단을 반환한다:

    3-1) 이전 '자식 노드' 재귀호출에서는 딱 '자식 자기 자신'까지만 포함한 상태로 깊이 판단을 하였을 것이므로, '형제 노드'와의 깊이 비교는 이루어지지 않았을 것이다. 따라서 '현재(부모) 노드'의 두 자식 노드의 깊이를 비교해주고, 2 이상 차이나면 - 1을 반환한다.

    3-2) 그렇지 않으면(두 자식의 깊이가 1만 차이나거나 같다면) 더 깊은 자식을 골라 1을 더한 현재까지의 깊이를 반환한다.

  • 위의 로직을 얻기 위한 생각의 흐름은 다음과 같다:

    (1)두 자식 트리의 깊이를 비교해야 한다 -> 두 자식 트리의 깊이를 각각 불러온다. (2)그렇게 불러온 두 깊이가 2 이상 차이나면 '균형 아님'으로 판단해야 한다 -> 두 깊이가 2 이상 차이나면 -1을 반환하도록 한다.

    (1)+(2)가 '현재 노드'에 대한 판단 로직이고, (1)을 재귀적으로 구할 수 있을 것 같다. 그렇다면 두 깊이가 2 이상 차이날 때 '균형 아님'으로 판단하는 것 뿐만 아니라 반환 결과값이 '현재 노드 이하 트리의 깊이'가 될 수 있도록 숫자값이 되어야 하고, 또 탈출 조건이 필요해진다:

    (3)두 자식 트리의 깊이가 2 이상 차이나면 '균형 아님'으로 -1을 반환하도록 만들고, 반대로 1 이하로 차이나면 '균형임'으로 현재 노드까지의 깊이값을 반환해주면 되겠다 -> 두 자식 트리 깊이가 같을 때 아무 자식의 깊이에 1을 더한 값을, 두 자식 트리 깊이가 1 차이날 때 더 깊은 자식의 깊이에 1을 더한 값을 반환한다. 즉, 두 자식 트리 중 더 깊은 자식의 깊이에 1을 더한 값이 '현재 노드' 레벨까지 추가한 현재 깊이가 된다.

    (4)탈출 조건은 처음에 깊이 숫자값이 시작되는 지점이기도 해야 한다. 즉, 탈출 반환값이 숫자값이 되어야 한다. 나 자신 노드를 레벨 하나로 셈하므로, 반대로 만약 나 자신 노드가 '없다면' 더해지는 레벨이 0인 것이다. 그렇다면 현재 노드가 null일 때 0을 반환하든지 현재 노드가 잎 노드일 때 1을 반환하든지 하여 탈출 조건을 짜면 되겠다.

    (5)엇 그런데 최종적으로 반환해야 하는 형태는 true/false의 불리언이다. 지금 만드는 재귀함수는 숫자값을 반환해야 하므로, 결국 본체 solution 함수 외에 보조 재귀함수를 만들어야 한다는 결론이 나온다.

  • 위의 로직을 구현한 코드:

    function solution6(root: TreeNode | null): boolean {
    
    	function subTreeDepth(node: TreeNode | null): number {
    		// 0. 탈출 조건: 현재 노드가 잎 노드이면 1을 반환하도록 한다.
    		// if (!node.left && !node.right && node) return 1;
    		if (!node) return 0;
    	
    		// 1. 두 자식 트리의 깊이를 각각 불러온다. 
    		const leftDepth = subTreeDepth(node.left); // node.left가 null일 때의 대처가 없다.
    		const rightDepth = subTreeDepth(node.right);
    		// 1-1. 
    		if (leftDepth === -1 || rightDepth === -1) return -1;
    
    		// 2. 그렇게 불러온 두 깊이가 2 이상 차이나면 '균형 아님'을, 즉 -1을 반환하도록 한다. 
    		if (Math.abs(leftDepth - rightDepth) > 1) return -1;
    		// => 둘의 결과값이 -1인 경우에는 '차' 계산값이 이상해진다. 결국 -1의 경우를 따로 취급해줘야 한다. -> 1.1 조건 추가. 
    		// 3. 반대로 깊이가 1 이하로 차이나면 '균형임'을, 즉 두 자식 트리 중 더 깊은 자식의 깊이에 '현재 노드'의 레벨까지 +1을 더한 값을 반환한다. 
    		return Math.max(leftDepth, rightDepth) + 1;
    	}
    
    	return subTreeDepth(root) !== -1;
    }

Uploaded by N2T