.leetcode(105. Construct Binary Tree from Preorder and Inorder Traversal)

문제

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

문제 풀기 전

1. preorder를 기준으로 inorder를 쪼개면 되겠다.
2. 이런문제 나오면 배열을 복제하고 싶지만 결코 그건 답이 될 수 없다.

직접 푼 풀이

소요시간: 74분(19:55 ~ 21:09)

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return makeTree(preorder, 0, inorder, 0, inorder.length);
    }

    public TreeNode makeTree(int[] preorder, int index, int[] inorder, int start, int end) {
        if (start >= end) {
            return null;
        }

        int midIndex = 0;
        int count = 0;
        for (int i=start; i<end; i++) {
            if (preorder[index] == inorder[i]) {
                midIndex = i;
                break;
            }
        }

        int leftStartIndex = index+1;
        int rightStartIndex = index+midIndex-start+1;
        TreeNode ret = new TreeNode(preorder[index]);
        ret.left = makeTree(preorder, leftStartIndex, inorder, start, midIndex);
        ret.right = makeTree(preorder, rightStartIndex, inorder, midIndex+1, end);
        return ret;
    }
}

느낀점

1. Tree에서 recursion을 할때면 머리에 쥐가 날거같다. 돈거 같고 아닌거 같고 그럴때는 중간 리턴 기대값을 생각해보면 좀 그래도 쉽다. ret.left나 ret.right가 뭐가 나와야되지를 생각하고 recursion을 되돌아보면 좀 괜찮아진다.
2. 솔루션보면 이런건 보통 전역변수를 썼는데 난 전역변수를 안쓰고 index움직임으로 제어했다는게 다르다.
3. 위의 코드에서는 int[] preorder의 인덱스를 index변수로 따라가고 int[] inorder의 범위는 start, end로 좁혀나가서 구하는 방식이다.

누적되는 알고리즘 접근 설명서

2021/01/09 - [알고리즘 풀이] - .leetcode(알고리즘 문제풀이 접근)