검지 Offer 면접 문제: 두 갈래 나무 재건

두 갈래 나무를 재건하다

제목은 어떤 두 갈래 나무의 앞 순서와 중간 순서를 입력한 결과를 설명합니다. 이 두 갈래 나무를 다시 만드십시오.입력한 앞 순서와 중간 순서의 결과에 중복된 숫자가 없다고 가정하십시오.예를 들어 앞 순서 반복 시퀀스 {1,2,4,7,3,5,6,8}와 중간 순서 반복 시퀀스 {4,7,2,1,5,3,8,6}를 입력하면 두 갈래 트리를 재건하고 되돌려줍니다.
분석

이것은 비교적 기초적인 두 갈래 나무 문제다

앞의 첫 번째 노드는 반드시 뿌리 노드이다. 먼저 뿌리 노드를 얻은 다음에 뿌리 절점의 중간의 순서를 이용하여 왼쪽 나무 부분 + 뿌리 노드 + 오른쪽 나무 부분으로 나눈다

그리고 좌우 나무의 처리 상황이 같다는 것을 발견하고 귀속시키면 된다

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if((pre.length <= 0 && in.length <= 0) || pre.length != in.length)
            return null;
        // 
        TreeNode root = new TreeNode(pre[0]);
        // 
        int middle = 0;
        for(int i=0; i < pre.length; i++){
            if(in[i] == pre[0])
                middle = i;
        }
        // ： 
        int[] new_pre_left = new int[middle];
        int[] new_pre_right = new int[in.length - middle - 1];
        int[] new_in_left = new int[middle];
        int[] new_in_right = new int[in.length - middle - 1];

        for(int i=0; i < middle; i++){
            new_pre_left[i] = pre[i+1];
            new_in_left[i] = in[i];
        }
        for(int i=0; i < in.length - middle - 1; i++){
            new_pre_right[i] = pre[i+middle+1];
            new_in_right[i] = in[i+middle+1];
        }
        // 
        root.left = reConstructBinaryTree(new_pre_left, new_in_left);
        root.right = reConstructBinaryTree(new_pre_right, new_in_right);

        return root;
    }
}

첫 번째 AC의 코드는 비교적 번거롭다. 자바 라이브러리 함수를 사용하면 후반부에 있는 수조에 대한 조작을 간소화할 수 있다

import java.util.*;
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if((pre.length <= 0 && in.length <= 0) || pre.length != in.length)
            return null;
        // 
        TreeNode root = new TreeNode(pre[0]);
        // 
        int middle = 0;
        for(int i=0; i < pre.length; i++){
            if(in[i] == pre[0])
                middle = i;
        }

        root.left = reConstructBinaryTree(Arrays.copyOfRange(pre,1,middle+1),Arrays.copyOfRange(in,0,middle));
        root.right = reConstructBinaryTree(Arrays.copyOfRange(pre,middle+1,in.length),Arrays.copyOfRange(in,middle+1,in.length));

        return root;
    }
}