Preorder and Inorder Traversal 에서 바 이 너 리 트 리 구축 | Java 최 단 코드 구현

원본 링크:
105. 순서 및 순서 횡단 에서 이 진 나 무 를 구축 관련 글:
106. Inorder 및 Postorder Traversal 에서 바 이 너 리 트 리 구축 | Java 최 단 코드 구현
[사고방식]
이 문 제 는 전 서 를 옮 겨 다 니 고 중 서 를 옮 겨 다 니 며 이 진 트 리 를 구성 해 왔 다.우 리 는 앞 순 서 를 옮 겨 다 니 는 첫 번 째 노드 가 뿌리 노드 라 는 것 을 알 고 있 습 니 다. 중간 순 서 를 옮 겨 다 니 는 과정 에서 이 노드 를 찾 았 습 니 다. 중간 순 서 를 앞 부분 으로 나 누 는 왼쪽 하위 트 리 의 순서 와 후반 부분의 오른쪽 하위 트 리 의 순서 로 옮 겨 다 니 며 이렇게 반복 합 니 다.

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return createTree(preorder, 0, inorder, 0, preorder.length - 1);
    }
    private TreeNode createTree(int[] preorder, int preIndex, int[] inorder, int inBeg, int inEnd) {
        if (preIndex >= preorder.length) return null;
        int findIndex = 0;
        for (int i = inBeg; i <= inEnd; i++)
            if (preorder[preIndex] == inorder[i]) {
                findIndex = i;
                break;
            }
        TreeNode root = new TreeNode(preorder[preIndex]);
        if (findIndex > inBeg)
            root.left = createTree(preorder, preIndex + 1, inorder, inBeg, findIndex - 1);
        if (findIndex < inEnd)
            root.right = createTree(preorder, preIndex + 1 + findIndex - inBeg, inorder, findIndex + 1, inEnd);
        return root;
    }

202 / 202
 test cases passed. Runtime: 21 ms  Your runtime beats 21.67% of javasubmissions.
최적화 환영 합 니 다!