leetcode-889-105-106- 전-중-후를 따라 두 갈래 나무 만들기

카탈로그

889. 전차와 후차에 따라 두 갈래 나무를 두루 구성한다

105. 이전 서열과 중간 서열을 두루 훑어보며 두 갈래 나무를 구성한다

106. 중순과 후순을 두루 돌아다니며 두 갈래 나무를 구성한다

분석

code

Posted by 마이크로박@Yangsc_o

원문, 저작권 성명: 자유전재-비상용-비파생-서명유지|Creative Commons BY-NC-ND 3.0

이 문제는 leetcode, 주소입니다.
889. 전차와 후차에 따라 두 갈래 나무를 반복적으로 구성한다.
105. 전차와 중차 역행 서열 구조 두 갈래 나무
106. 중차순과 후차순 역행 서열 구조 두 갈래 나무

제목

889. 전차와 후차에 따라 두 갈래 나무를 반복적으로 구성한다.

주어진 전차와 후차와 일치하는 두 갈래 트리를 되돌려줍니다.
pre와post가 두루 다니는 값은 서로 다른 정수입니다.
예:
입력: pre = [1,2,4,5,3,6,7],post = [4,5,2,6,7,3,1] 출력: [1,2,3,4,5,6,7]
팁:
1 <= pre.length == post.length<=30 pre[]와post[]는 모두 1, 2,......,pre.length의 배열은 입력마다 적어도 하나의 답이 있어야 한다.만약 여러 개의 답이 있다면, 그 중 하나로 돌아갈 수 있다.
한 그루의 나무의 전차적 역류와 중차적 역류에 따라 두 갈래 나무를 구성한다.
주의: 트리에 중복된 요소가 없다고 가정할 수 있습니다.
예를 들어

105. 전차와 중차 역행 서열 구조 두 갈래 나무

전차 역행 preorder = [3,9,20,15,7] 중차 역행 inorder = [9,3,15,20,7] 아래의 두 갈래 나무로 돌아가기: 3/9 20/15 7

106. 중차순과 후차순 역행 서열 구조 두 갈래 나무

한 그루의 나무의 중차 역류와 후차 역류에 따라 두 갈래 나무를 구성한다.
주의: 트리에 중복된 요소가 없다고 가정할 수 있습니다.
예를 들어
inorder = [9,3,15,20,7] 뒷차례postorder = [9,15,7,20,3] 아래의 두 갈래 나무로 되돌아가기: 3/9 20/15 7

분석

사실 이 세 가지 문제는 매우 유사하다. 문제를 푸는 전제는 나무의 앞차례 역력, 중차례 역력, 후속 역력의 특징을 이해해야 한다.

앞차례 훑어보기: 훑어보기 순서, 뿌리-좌-우;첫 번째 노드는 바로 뿌리 노드이다

중서 역력: 역력 순서, 왼쪽-뿌리-오른쪽;뿌리 노드는 좌우 나무를 구분하는 노드이다

후속 반복: 반복 순서, 왼쪽-오른쪽-뿌리;이로부터 알 수 있듯이 뿌리 노드는 마지막이다

[889. 앞의 순서와 뒤의 순서에 따라 두 갈래 트리 구성]:
앞의 역주행과 뒤의 역주행 특징에 따라 우리는 앞의 역주행 중의 첫 번째 비뿌리 노드가 두 번째 노드에 있는 위치를 찾으면 각각 분리할 수 있다. 앞의 역주행: (뿌리) (왼쪽 나무) (우측 나무) (우측 나무) (우측 나무) (뿌리) 이렇게 하면 우리는 뿌리 노드를 얻을 수 있다. 각각 왼쪽 나무와 오른쪽 나무에 대해 역귀 작업을 하고 그 뿌리 노드를 각각 얻을 수 있다.이렇게 하면 온전한 나무를 얻을 수 있다.
같은 이치로 우리는 전+중을 분석할 수 있다.중+후의 추정 논리;
한 네티즌은 다음과 같이 요약했다.
전+후 우선 현재 루트 노드가pre[pre_start]이고 뒷순서에 있는post_end, 그래서 우리는 좌우 나무를 구분할 수 있는 노드를 찾아야 한다.우리는 왼쪽 트리의 루트 노드가pre[pre_start+1]인 것을 알고 있기 때문에 뒷순서에 있는 위치를 찾으면 왼쪽 트리(index의 의미) 앞+에서 먼저 우리는 현재 루트 노드가pre[pre_start]라는 것을 분명히 알 수 있다. 중간 순서에 있는 위치만 찾으면 왼쪽 트리를 분리할 수 있다. (index의 의미) 중+에서 먼저 우리는 현재 루트 노드가post[post_end]라는 것을 분명히 알 수 있다.그것의 중서에 있는 위치만 찾아내면 좌우 트리를 분리할 수 있다 (index의 의미)

code

    // 889.  
    public TreeNode constructFromPrePost(int[] pre, int[] post) {
        if(pre==null || pre.length==0) {
            return null;
        }
        TreeNode root = new TreeNode(pre[0]);
        int length = pre.length;
        if(length == 1) {
            return root;
        }
        for(int index =0; index < length; index ++) {
            if(pre[1] == post[index]) {
                int[] pre_left = Arrays.copyOfRange(pre,1,index + 1 + 1);
                int[] pre_right = Arrays.copyOfRange(pre,index + 1 + 1 ,length);

                int[] post_left = Arrays.copyOfRange(post,0,index);
                int[] post_right = Arrays.copyOfRange(post,index + 1, length -1);

                root.left = constructFromPrePost(pre_left,post_left);
                root.right = constructFromPrePost(pre_right,post_right);
                break;
            }
        }
        return root;
    }


   // 105.  
	 public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder == null || preorder.length == 0) {
            return null;
        } 
       
        int length = preorder.length;  
        TreeNode root =  new TreeNode(preorder[0]);
        if(length == 1) {
            return root;
        }

        for(int index = 0; index < length; index ++) {
            if(root.val == inorder[index]) {
                int[] preorder_left = Arrays.copyOfRange(preorder,1,index + 1);
                int[] preorder_right = Arrays.copyOfRange(preorder,index + 1, length);

                int[] inorder_left =  Arrays.copyOfRange(inorder,0,index);
                int[] inorder_right = Arrays.copyOfRange(inorder,index + 1,length);

                root.left = buildTree(preorder_left,inorder_left);
                root.right = buildTree(preorder_right,inorder_right);
                break;
            }
        }
        return root;
    }	



   // 106.  
   public TreeNode buildTree(int[] inorder, int[] postorder) {
        if(postorder == null || postorder.length == 0) {
            return null;
        }
        
        int length = postorder.length;
        if(length == 1){
             return new TreeNode(postorder[length -1]);
        }

        TreeNode root = new TreeNode(postorder[length - 1]);
        for(int index = 0; index < length; index ++) {
            if(postorder[length -1] == inorder[index]) {
                int[] inorder_left = Arrays.copyOfRange(inorder,0,index);
                int[] inorder_right = Arrays.copyOfRange(inorder,index + 1,length);

                int[] postorder_left = Arrays.copyOfRange(postorder,0,index);
                int[] postorder_right = Arrays.copyOfRange(postorder,index,length -1);

                root.left = buildTree(inorder_left,postorder_left);
                root.right = buildTree(inorder_right,postorder_right );
                break;
            }
        }

        return root;
    }

너의 격려도 나의 창작의 동력이다

포상 주소