JavaDS--두 갈래 나무의 환원 상해

한 그루의 나무의 전 순서와 중 순서에 따라 두 갈래 나무의 힘줄 연결을 구성한다.이전 순서에서 결과를 옮겨다니며 나무 뿌리 노드의 내용을 얻습니다.중간 순서 반복 결과에서 루트의 위치pos를 찾은 다음 중간 순서 데이터를 좌우로 나누기 [left,pos) [pos+1,right) 3. 루트 노드 만들기

루트 노드를 만드는 왼쪽 트리

귀속

루트 노드를 만드는 오른쪽 트리

귀속

class Solution {
    int index=0;
    //[left,right)
    private TreeNode reBuilidTree(int[] preorder,int[] inorder, int left,int right){
        if(left>=right || index >= preorder.length){
            return null;
        }
        //       
        //     
        TreeNode root =new TreeNode(preorder[index]);

        //             
        //             
        int inrootIdx=left;
        while(inrootIdx<right){
            if(inorder[inrootIdx] == preorder[index])
                break;
            inrootIdx++;
        }
        ++index;
        //           
        root.left=reBuilidTree(preorder,inorder,left,inrootIdx);

        //           
        root.right=reBuilidTree(preorder,inorder,inrootIdx+1,right);

        return root;
    }
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        index=0;
        return reBuilidTree(preorder,inorder,0,inorder.length);
    }
}

한 그루의 나무의 중간 순서와 뒤 순서에 따라 두 갈래 나무의 힘줄 연결을 구성한다.결과에서 추출한 루트 노드의 값 필드를 후순으로 옮겨다니기 2.중간 반복 결과에서 루트 노드의 위치를 찾으면 중간 반복 결과를 좌우 두 부분으로 나눌 수 있습니다

왼쪽 트리의 노드 데이터: [left,rootidx)

오른쪽 트리의 노드 데이터: [rootidx+1,right) 3. 루트 노드 만들기

루트 노드를 만드는 왼쪽 트리

귀속

루트 노드를 만드는 오른쪽 트리

귀속

class Solution {
    int index = 0;
    private TreeNode buildTree(int[] inorder, int[] postorder,int left,int right) {
        if(left>=right || index<0){
            return null;
        }


        int inrootidx=left;
        while(inrootidx<right){
            if(inorder[inrootidx]==postorder[index])
                break;
            ++inrootidx;
        }

        TreeNode root=new TreeNode(postorder[index]);
        --index;
        // 
        root.right=buildTree(inorder,postorder,inrootidx+1,right);
        // 
        root.left=buildTree(inorder,postorder,left,inrootidx);
        return root;
    }
    public TreeNode buildTree(int[] inorder, int[] postorder){
        index=postorder.length-1;
        return buildTree(inorder,postorder,0,inorder.length);
    }
}