9/26 (화) 이진 트리 후위 순회 구현 TIL

공부한 것

• LeetCode #145. Binary Tree Postorder Traversal

  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/binary-tree-postorder-traversal/description/

  

  후위 순회(Postorder traversal): ‘나’와 두 자식을 기준으로, “왼 자식 → 오른 자식 → 나” 순으로 순회하는 것.

  어제 구현한 중위 순회를 바탕으로 빠르게 풀 수 있었다. Iterative 방식으로 풀이 중에 오른쪽 자식을 처리하는 부분을 추가할 때 else if로 할지 왼쪽 자식과 함께 ‘자식이 존재하면’의 큰 if로 묶어줘야 하는지 고민했는데, else if로 괜찮았던 것으로.

  • 순회(iterative) 해답:

    // iterative solution
    function postorderTraversal1(root: TreeNode | null): number[] {
    	if (!root) return [];
    
    	const resultMap: Map<TreeNode, number> = new Map();
    	const stack: TreeNode[] = [root];
    
    	while (stack.length) {
    		// 지금 노드를 '본다'
    		const node = stack[stack.length - 1];
    		
    		// 왼쪽 노드가 있고 아직 '처리'하지 않았다면 왼쪽 자식을 스택에 추가한다. 
    		if (node.left && !resultMap.has(node.left)) stack.push(node.left);
    		// 그렇지 않고(?) 오른쪽 노드가 있고 아직 '처리'하지 않았다면 오른 자식을 스택에 추가한다. 
    		else if (node.right && !resultMap.has(node.right)) stack.push(node.right);
    		// 그렇지 않다면(양 자식이 없거나 모두 처리된 경우) 현재 노드를 스택에서 뽑고, result에 넣는다. 
    		else {
    			stack.pop();
    			resultMap.set(node, node.val);
    		}
    	}
    
    	return [...resultMap.values()];
    }

  • 재귀(recursive) 해답:

    // recursive solution
    function postorderTraversal2(root: TreeNode | null): number[] {
    	if (!root) return [];
    	return [...postorderTraversal2(root.left), ...postorderTraversal2(root.right), root.val];
    }

Uploaded by N2T