[Grind75-LeetCode] Construct Binary Tree from Preorder and Inorder Traversal JAVA

반응형

728x90

[Grind75-LeetCode]

Construct Binary Tree from Preorder and Inorder Traversal - Medium

---

접근

• dfs

---

풀이

전위 순회, 중위 순회 순서가 담긴 배열을 통해 이진트리를 만들어내는 문제이다. 전위 순회의 경우 루트 -> 왼쪽 서브트리 -> 오른쪽 서브트리 순서로 순회가 되고 중위 순회의 경우 왼쪽 서브트리 -> 루트 -> 오른쪽 서브트리 순서로 순회가 된다. 즉 전위 순회 배열을 루트로 사용하고 중위 순회 배열을 통해 양쪽 서브트리를 찾는 방식으로 진행해야 한다.

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return treeBuilder(preorder, inorder, 0, 0, inorder.length - 1);
    }

treeBuilder라는 메서드로 재귀를 통해 트리를 구성하게 된다. 

    private TreeNode treeBuilder(int[] preorder, int[] inorder, int preStart, int inStart, int inEnd) {
        if (preStart >= preorder.length || inStart > inEnd) {
            return null;
        }

        int rootVal = preorder[preStart];
        TreeNode root = new TreeNode(rootVal);

우선 전위 순회의 인덱스가 배열의 길이보다 같거나 크다면 모든 노드에 대해 처리가 끝나 더 이상 연결할 서브트리가 없다고 생각하면 된다. 전위 순회 배열의 값을 루트로 사용하여 루트 노드를 만들어준다.

	int rootIndex = -1;
        for (int i = inStart; i <= inEnd; i++) {
            if (inorder[i] == rootVal) {
                rootIndex = i;
                break;
            }
        }

중위 순회 배열에서 루트 노드를 만들 때 사용했던 트리의 값을 찾아준다. 중위 순회는 왼쪽 -> 루트 -> 오른쪽 형태로 순회가 되기 때문에 루트 노드의 값을 찾게 되면 해당 인덱스를 기준으로 왼쪽은 왼쪽 서브트리, 오른쪽은 오른쪽 서브트리로 나눌 수 있게 된다. 

preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]

root = 3 inorder[1] = 3
1번 인덱스를 기준으로
왼쪽 서브트리: 9
오른쪽 서브트리:15, 20, 7

나눠진 서브트리를 기준으로 재귀적으로 진행하게 된다.

	int leftSize = rootIndex - inStart;

        root.left = treeBuilder(preorder, inorder, preStart + 1, inStart, rootIndex - 1);
        root.right = treeBuilder(preorder, inorder, preStart + leftSize + 1, rootIndex + 1, inEnd);

        return root;
    }

위에서 찾은 중위 순회 배열의 인덱스를 기준으로 루트와 연결될 왼쪽, 오른쪽 서브트리를 재귀를 통해 찾게 된다. 왼쪽의 경우 다음 루트 노드는 전위 순회의 다음 인덱스가 되고 중위 순회 배열에서의 범위는 루트 인덱스를 기준으로 왼쪽 범위에서 진행하게 된다. 오른쪽 서브트리의 경우 루트 인덱스를 기준으로 오른쪽 범위에서 진행하게 된다.

left -> root 9 중위 순회 범위 0~0
rigth -> root 20 중위 순회 범위 2~4

기본

---

HashMap

매번 재귀 호출마다 for문을 통해 중위 순회 배열에서 인덱스를 찾다 보니 연산이 많이 발생했다. 1ms, 2ms 코드엔 HashMap을 사용해 미리 중위 순회 배열에서 인덱스를 찾아 매핑해 둔 뒤 사용했다. 

    public TreeNode buildTree(int[] preorder, int[] inorder) {
	int n = preorder.length;
        HashMap<Integer,Integer> mpp = new HashMap<Integer,Integer>();
        for(int i =0;i<n;i++)
        {
            mpp.put(inorder[i],i);
        }
        TreeNode root = build(preorder,0,n-1,inorder,0,n-1,mpp);

       return root;
    }

 중위 순회 배열을 미리 탐색하여 각 노드 값에 대해 인덱스를 매핑해 둔다.

    private TreeNode build(int[] preorder, int prestart,int preend, int[] inorder,int instart, int inend, HashMap<Integer,Integer> mpp)
    {
        if(prestart > preend || instart > inend)
        return null;
        TreeNode root = new TreeNode(preorder[prestart]);
        int inroot = mpp.get(root.val);
        int numsleft = inroot - instart;
        root.left = build(preorder,prestart+1,prestart+numsleft,inorder,instart,inroot-1,mpp);
        root.right = build(preorder,prestart+numsleft+1,preend,inorder,inroot+1,inend,mpp);
        return root;
    }

트리를 구성하는 코드 자체는 동일한 방식으로 진행된다.

---

0ms

1,2, 3ms와 0ms 간의 제출률이 차이가 나기 때문에 코드 리뷰를 하고 넘어가야 된다고 생각한다. 0ms 코드는 굉장히 단순하게 쓰인 코드였다. 똑같이 재귀를 통한 dfs로 풀어졌지만 차이라 할 만한 건 인덱스를 전역 변수로 선언해 관리했다.

    int preIndex = 0;
    int inIndex = 0;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return dfs(preorder, inorder, Integer.MAX_VALUE);
    }

각 배열에 사용될 인덱스를 전역으로 선언했다.

    private TreeNode dfs(int[] preorder, int[] inorder, int limit) {
        if (preIndex >= preorder.length) {
            return null;
        }

        if (inorder[inIndex] == limit) {
            inIndex++;
            return null;
        }

        TreeNode root = new TreeNode(preorder[preIndex++]);
        root.left = dfs(preorder, inorder, root.val);
        root.right = dfs(preorder, inorder, limit);

        return root;
    }

중위 순회 배열에 사용하는 범위 인덱스를 시작점만 다루다 보니 전위 순회 배열을 끝까지 반복했을 때의 처리만 존재했다. limit 변수를 통해 체크를 해주게 되는데 현재 노드가 서브트리의 경계를 넘어섰는지 확인한다. limit의 값은 부모 노드의 값으로 설정되며 해당 값 보다 작은 값은 왼쪽 서브트리, 큰 값을 오른쪽 서브트리가 되는 것이다. 왼쪽 서브트리의 경우 해당 부모 값인 limit를 만나게 된다면 해당 노드는 부모를 기준으로 왼쪽 서브트리에 존재해선 안 되는 오른쪽 서브트리에 존재할 값이기 때문에 inIndex 값을 올려 자식 노드를 해당 부모 노드 오른쪽으로 보내는 개념이 아닌 부모 노드의 값을 올려 자식 노드가 알맞은 부모 노드 밑으로 가게 해주는 개념이다. 위에 다른 코드들 보단 직관적으로 이해하기 조금 힘든 부분이 있는 거 같지만 코드는 간결하고 성능은 좋아졌다.

 

---

전체 코드

기본

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return treeBuilder(preorder, inorder, 0, 0, inorder.length - 1);
    }

    private TreeNode treeBuilder(int[] preorder, int[] inorder, int preStart, int inStart, int inEnd) {
        if (preStart >= preorder.length || inStart > inEnd) {
            return null;
        }

        int rootVal = preorder[preStart];
        TreeNode root = new TreeNode(rootVal);

        int rootIndex = -1;
        for (int i = inStart; i <= inEnd; i++) {
            if (inorder[i] == rootVal) {
                rootIndex = i;
                break;
            }
        }

        int leftSize = rootIndex - inStart;

        root.left = treeBuilder(preorder, inorder, preStart + 1, inStart, rootIndex - 1);
        root.right = treeBuilder(preorder, inorder, preStart + leftSize + 1, rootIndex + 1, inEnd);

        return root;
    }
}

 

HashMap

 /**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
int n = preorder.length;
        HashMap<Integer,Integer> mpp = new HashMap<Integer,Integer>();
        for(int i =0;i<n;i++)
        {
            mpp.put(inorder[i],i);
        }
        TreeNode root = build(preorder,0,n-1,inorder,0,n-1,mpp);

       return root;
    }
    private TreeNode build(int[] preorder, int prestart,int preend, int[] inorder,int instart, int inend, HashMap<Integer,Integer> mpp)
    {
        if(prestart > preend || instart > inend)
        return null;
        TreeNode root = new TreeNode(preorder[prestart]);
        int inroot = mpp.get(root.val);
        int numsleft = inroot - instart;
        root.left = build(preorder,prestart+1,prestart+numsleft,inorder,instart,inroot-1,mpp);
        root.right = build(preorder,prestart+numsleft+1,preend,inorder,inroot+1,inend,mpp);
        return root;
    }
}

 

0ms

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int preIndex = 0;
    int inIndex = 0;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return dfs(preorder, inorder, Integer.MAX_VALUE);
    }

    private TreeNode dfs(int[] preorder, int[] inorder, int limit) {
        if (preIndex >= preorder.length) {
            return null;
        }

        if (inorder[inIndex] == limit) {
            inIndex++;
            return null;
        }

        TreeNode root = new TreeNode(preorder[preIndex++]);
        root.left = dfs(preorder, inorder, root.val);
        root.right = dfs(preorder, inorder, limit);

        return root;
    }
}