TIL | WIL

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

깊은바다거북 2023. 9. 12. 21:13

공부한 것

  • 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);
      }
    1. 스택을 이용한 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