[코딩 테스트 합격자 되기] 문제 26 트리 순회

문제 설명

이진 트리를 표현한 배열 node를 인자로 받습니다. 예를 들어서 nodes가 [1,2,3,4,5,6,7]이면 다음과 같은 트리를 표현한 것입니다. 해당 이진 트리에 대하여 전위 순회, 중위 순회, 후위 순회 결과를 반환하는 solution()함수를 구현하세요.

 

제약 조건

• 입력 노드값의 개수는 1개 이상 1000개 이하이다.
• 노드값은 정수형이며, 중복되지 않는다.

입출력의 예

nodes	return
[1,2,3,4,5,6,7]	["1 2 4 5 3 6 7", "4 2 5 1 6 3 7", "4 5 2 6 7 3 1"]

 

정답

const preorder(nodes, idx){
	//전위순회(부왼오)
    if(idx < nodes.length){
    	//노드 배열의 길이보다 인덱스가 작을때
        let ret = `${nodes[idx]}`; //루트노드를 먼저 출력한다.(부)
        ret += preorder(nodes, idx * 2 + 1) //인덱스로 돌리니깐 원래는 왼쪽이 i*2이지만 i*2+1로(왼)
        ret += preorder(nodes, idx * 2 + 2) //이것도 오른쪽으로 i*2+1이지만 i*2+2(오)
        return ret;
    }
    
    //idx가 같거나 작으면 빈 문자열 반환
    return "";
} 

const inorder(nodex,idx){
	//중위순회(왼부오)
    if(idx < nodes.length){
    	let ret = inorder(nodes, idx*2+1);
        ret += `${nodes[idx]}`;
        ret += inorder(nodes, idx*2+2);
        return ret;
    }
    
    return "";
}

const postorder(nodes,idx){
	//후위순회(왼오부)
    if(idx < nodes.length){
    	let ret = postorder(nodes, idx*2+1);
        ret += postorder(nodes, idx*2+2);
        ret += `${nodes[idx]}`;
        return ret;
    }
    
    return "";
}

solution(nodes){
	//slice는 마지막 공백 제거
	return [preorder(nodes,0).slice(0,-1),inorder(nodes,0).slice(0, -1),postorder(nodes,0).slice(0,-1)];
}