LeetCode 105. Construct Binary Tree from Preorder and Inorder Traversal 자바 문제 풀이

문제

Construct Binary Tree from Preorder and Inorder Traversal - LeetCode

문제 해결 방법

• inorder와 preorder를 입력받아서 BFS로 출력하라는 문제입니다.
• inorder와 preorder의 특징을 사용하여, BFS로 출력해야 합니다.
• 참고 링크
• 그래프 탐색: DFS,BFS 트리: inorder, preorder, postorder
• preorder의 특징은 root, left, right순으로 출력이 된다는 것입니다. 가장 먼저오는 노드는 무조건 root노드 입니다.
• inorder의 특징은 left, root, right 순으로 출력이 된다는 것입니다. 루트노드만 알면, 왼쪽과 오른쪽에 어떤 노드가 올지 알수 있습니다.
• 알고리즘
  • preorder의 첫번째 노드가 루트노드입니다.
  • 루트노드를 알고있으므로, 왼쪽과 오른쪽의 subtree를 선별할수 있습니다.
  • 선별된 subtree에서 preorder의 첫번째 노드가 루트노드 입니다.
  • 이를 반복한다면 전체 노드를 알수 있고, BFS출력을 할수 있습니다.
  • 전에 계산한 값이 필요하고, 반복적인 subtree를 계산해야 하므로, 재귀함수를 사용해야 합니다.

재귀함수

• 목표: Construct Binary Tree from Preorder and Inorder Traversal
• 종료 조건: 각 오더의 start가 end를 넘어설 경우

inStart>inEnd || preStart>preEnd return null

• 이전단계의 결과가 필요한가?: yes
• 작은 하위 문제: 루트인덱스 판별, 루트 값을 이용하여 inorder의 인덱스 찾기

resultRoot=pre[0]; 
for(inorder) 
	find pre[0] in inorder, save index 
	inorderIndex that has value as pre[0]

• 결과의 조합: 각 루트노드를 순차적으로 입력(BFS순)

resultRoot.left=left subtree 
resultRoot.right=right subtree 

//end of method 
return resultRoot

• 다음 단계로 가기전 변경 할점: subtree선택

root=pre[0]
왼쪽
preStart=preStart+1(root node)
preEnd=preEnd-num of right Nodes
inStart=inStart
inEnd=inIndex that has pre[0]-1
오른쪽
preStart=preStart+num of left Nodes+1(root node)
preEnd=preEnd
inStart=inIndex that has pre[0]+1
inEnd=inEnd

Github Link

https://github.com/eunhanlee/LeetCode_105_ConstructBinaryTreefromPreorderandInorderTraversal_Solution.git

시간복잡도: O(n), 공간복잡도: O(n)

import java.util.HashMap;

public class Solution {
    //inorder 인덱스값을 빠르게 찾기위한 해쉬맵 선언
    private HashMap<Integer, Integer> inorderIndexMap;

    /**
     * 주어진 preorder 순회 배열과 inorder 순회 배열을 사용하여 이진 트리를 구성합니다.
     *
     * @param preorder preorder 순회 배열
     * @param inorder  inorder 순회 배열
     * @return 구성된 이진 트리의 루트 노드
     * @throws IllegalArgumentException 주어진 입력이 잘못된 경우 (inorder 배열에 루트 값이 없는 경우)
     */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        //문제에서 제약이 없으므로 삭제
//        if (preorder == null || inorder == null || preorder.length == 0 || inorder.length == 0)
//            return null;

        // inorder 배열의 각 값과 인덱스를 매핑한 해시맵 생성
        inorderIndexMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inorderIndexMap.put(inorder[i], i);
        }

        // 재귀적으로 이진 트리 구성 시작
        return buildTreeRecur(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
    }

    /**
     * 재귀적으로 이진 트리를 구성하는 보조 메서드입니다.
     *
     * @param preorder preorder 순회 배열
     * @param inorder  inorder 순회 배열
     * @param preStart 현재 서브트리의 preorder 시작 인덱스
     * @param preEnd   현재 서브트리의 preorder 끝 인덱스
     * @param inStart  현재 서브트리의 inorder 시작 인덱스
     * @param inEnd    현재 서브트리의 inorder 끝 인덱스
     * @return 구성된 서브트리의 루트 노드
     * @throws IllegalArgumentException 주어진 입력이 잘못된 경우 (inorder 배열에 루트 값이 없는 경우)
     */
    private TreeNode buildTreeRecur(int[] preorder, int[] inorder, int preStart, int preEnd, int inStart, int inEnd) {
        // 베이스 케이스: 인덱스 범위를 초과한 경우 빈 서브트리 반환
        if (inStart > inEnd || preStart > preEnd)
            return null;

        // 현재 서브트리의 루트 값 선택
        int currentRootValue = preorder[preStart];
        // 루트 값 리턴을 위한 새 노드 생성
        TreeNode resultRoot = new TreeNode(currentRootValue);

        // inorder 배열에서 루트 값의 인덱스 찾기
        Integer rootIndexInorder = inorderIndexMap.get(currentRootValue);
        //문제에서 제약이 없으므로 삭제
//        if (rootIndexInorder == null)
//            throw new IllegalArgumentException("Invalid input: root value not found in inorder array.");

        // 왼쪽 서브트리 구성
        resultRoot.left = buildTreeRecur(preorder, inorder, preStart + 1, preEnd, inStart, rootIndexInorder - 1);

        // 오른쪽 서브트리 구성
        resultRoot.right = buildTreeRecur(preorder, inorder, preStart + (rootIndexInorder - inStart) + 1, preEnd, rootIndexInorder + 1, inEnd);

        // 구성된 서브트리의 루트 노드 반환
        return resultRoot;
    }
}