[LeetCode] 99. Recover Binary Search Tree

😎풀이

지문에서 언급되어 있듯 정확히 두 노드가 잘못 되었다는 표기가 있기에 풀이가 한층 더 수월하다.

중위 순회로 변경 위치의 첫 노드를 잡고 부모를 기준으로 올라오며 문제가 되는 최상위 노드와 변경해주면 해결된다.

function recoverTree(root: TreeNode | null): void {
    // 중위 순회 결과를 저장할 배열
    const inorder: TreeNode[] = [];
    
    // 중위 순회 함수 (왼쪽 -> 루트 -> 오른쪽)
    function traverse(node: TreeNode | null): void {
        if (!node) return;
        traverse(node.left);
        inorder.push(node);
        traverse(node.right);
    }
    
    // 트리 순회 실행
    traverse(root);
    
    // 잘못된 노드 찾기
    let first: TreeNode | null = null;
    let second: TreeNode | null = null;
    
    // 배열을 순회하면서 순서가 잘못된 노드들 찾기
    for (let i = 0; i < inorder.length - 1; i++) {
        if (inorder[i].val > inorder[i + 1].val) {
            // 첫 번째 잘못된 노드를 찾았을 때
            if (!first) {
                first = inorder[i];
            }
            // 두 번째 잘못된 노드
            second = inorder[i + 1];
        }
    }
    
    // 찾은 두 노드의 값을 교환
    if (first && second) {
        const temp = first.val;
        first.val = second.val;
        second.val = temp;
    }
}