9/12 (화) 재귀를 스스로 풀다 TIL

공부한 것

• LeetCode #1448. Count Good Nodes in 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/count-good-nodes-in-binary-tree/

  

  ⇒ 어제에 이어서 스스로 풀어본 해답이 통했다! (스택을 이용한 해답은 다른 사람들의 해답을 참고함.) 재귀를 이용한 DFS도, 스택을 이용한 DFS도 이제 조금 홀로서기할 수 있을 것 같다.

  1. 재귀를 이용한 DFS:

     function solution1(root: TreeNode | null): number {
     	// 현재 노드 포함 모든 자식 노드 중 '착한' 노드 개수를 반환한다. 
     	function count(node: TreeNode | null, maxVal: number): number {
     		// 탈출 조건(Base condition): 현재 노드가 null이면 0을 반환한다. (=> 잎 노드는 양쪽 자식으로부터 0과 0을 반환받게 된다)
     		if (!node) return 0;
     
     		// 1) 자기 자신 노드가 '착한'노드인지 여부(+1 혹은 +0) 더하기
     		// 2) 왼쪽 자식 트리의 '착한'노드 누적 개수 더하기
     		// 3) 오른쪽 자식 트리의 '착한'노드 누적 개수를 더하여 반환한다.
     		return +(node.val >= maxVal) +
     		// return (node.val >= maxVal ? 1 : 0) +
     			count(node.left, Math.max(maxVal, node.val)) +
     			count(node.right, Math.max(maxVal, node.val));
     	}
     
     	return count(root, root.val);
     }

  2. 스택을 이용한 DFS:

     // 다른 해답: 스택에 최고값도 같이 저장해서 넘겨주는 방식으로 순회(iterative)함.
     function solution3(root: TreeNode | null): number {
     	const stack: Array<[TreeNode, number]> = [[root, root.val]];
     	let count:number = 0;
     
     	while (stack.length) {
     		const [node, currentMax] = stack.pop();
     		count += (node.val >= currentMax ? 1 : 0);
     
     		for (let child of [node.left, node.right]) {
     			if (child) {
     				stack.push([child, Math.max(node.val, currentMax)]);
     			}
     		}
     		// if (node.left) stack.push([node.left, Math.max(node.val, currentMax)]);
     		// if (node.right) stack.push([node.right, Math.max(node.val, currentMax)]);
     	}
     
     	return count;
     }

Uploaded by N2T