공부한 것
- LeetCode #1448. Count Good Nodes in Binary Tree
⇒ 어제에 이어서 스스로 풀어본 해답이 통했다! (스택을 이용한 해답은 다른 사람들의 해답을 참고함.) 재귀를 이용한 DFS도, 스택을 이용한 DFS도 이제 조금 홀로서기할 수 있을 것 같다.
- 재귀를 이용한 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); }
- 스택을 이용한 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; }
- 재귀를 이용한 DFS:
Uploaded by N2T