앞의 순서와 중간의 순서에 따라 두 갈래 나무를 구성하다

2633 단어 递归二叉树遍历
사고방식: 앞의 첫 번째 알파벳은 나무의 뿌리 노드이다. 그리고 중서 서열에 있는 이 알파벳의 위치를 본다. 앞의 알파벳은 왼쪽 트리이고, 뒤의 알파벳은 오른쪽 트리이다. 그리고 각각 이 두 개의 하위 트리의 앞순서와 중서 서열에 대해 귀속 조작을 한다.
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        int n = pre.length;
        TreeNode root = new TreeNode(pre[0]);
        int leftLen = 0;
        for(leftLen=0;leftLen<n&&pre[0]!=in[leftLen];leftLen++);
        int rightLen = n - leftLen - 1;
        int left1[] = new int[leftLen];
        int right1[] = new int[rightLen];
        int left2[] = new int[leftLen];
        int right2[] = new int[rightLen];
        for(int i=1;i<=leftLen;i++){
            left1[i-1] = pre[i];
            left2[i-1] = in[i-1];

        }
        for(int i=0;i<rightLen;i++){
            right1[i] = pre[leftLen+i+1];
            right2[i] = in[leftLen+i+1];
        }
        if(leftLen>0){
            root.left = reConstructBinaryTree(left1,left2);
        }
        if(rightLen>0){
            root.right = reConstructBinaryTree(right1,right2);
        }
        return root;

    }

좋은 웹페이지 즐겨찾기