106. Inorder 및 Postorder Traversal 에서 바 이 너 리 트 리 구축 | Java 최 단 코드 구현

원본 링크:
Inorder 와 Postorder Traversal 에서 Binary Tree 를 구축 합 니 다.
Preorder and Inorder Traversal 에서 바 이 너 리 트 리 구축 | Java 최 단 코드 구현
[사고방식]
이 문 제 는 중 서 를 옮 겨 다 니 고 후 서 를 옮 겨 다 니 며 이 진 트 리 를 구성 합 니 다.그 기본 적 인 사 고 는 바로 뒷 순 서 를 옮 겨 다 니 는 마지막 수의 값 을 찾 은 다음 에 중간 순 서 를 옮 겨 다 니 며 이 값 을 찾 는 것 이다.이 값 을 뿌리 로 하여 중간 순 서 를 왼쪽, 오른쪽 하위 트 리 서열 로 나 누 었 습 니 다. 앞의 순 서 는 왼쪽 하위 트 리 의 중간 순서 로 나 누 었 고 뒤의 순 서 는 오른쪽 하위 트 리 의 중간 순서 로 나 누 었 습 니 다.이 상태 에서 좌우 하위 트 리 로 돌아 가기:

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return createTree(inorder, 0, postorder.length - 1, postorder,
                postorder.length - 1);
    }
    private TreeNode createTree(int[] inorder, int inBeg, int inEnd,
            int[] postorder, int postIndex) {
        if (postIndex < 0) return null;
        int mid = 0;
        for (int i = inBeg; i <= inEnd; i++)
            if (inorder[i] == postorder[postIndex]) {
                mid = i;
                break;
            }
        TreeNode root = new TreeNode(inorder[mid]);
        if (mid - inBeg > 0)  //            0。   postIndex - (inEnd - mid) - 1          postorder    
            root.left = createTree(inorder, inBeg, mid - 1, postorder, postIndex - (inEnd - mid) - 1);
        if (inEnd - mid > 0)  //            0。   <span style="font-family: Arial, Helvetica, sans-serif;">postIndex - 1          postorder    </span>
            root.right = createTree(inorder, mid + 1, inEnd, postorder, postIndex - 1);
        return root;
    }

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