우객망_검지 Offer_04_전차 중차 재건 두 갈래 나무

1. 제목 설명

두 갈래 나무의 앞 순서와 중간 순서의 결과를 입력하십시오. 이 두 갈래 나무를 다시 만드십시오.입력한 앞 순서와 중간 순서의 결과에 중복된 숫자가 없다고 가정하십시오.예를 들어 앞 순서 반복 시퀀스 {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; }
 * }
 */

생각

1. 코드를 쓰기 전에 우리는 어떻게 전차순과 중차순에 따라 두 갈래 나무를 구축하고 수동으로 구축 과정을 시뮬레이션하는지 이해해야 한다
전차 서열의 첫 번째 노드는 반드시 루트 노드이다. 중차 역행 서열에서 이 루트 노드의 상응하는 위치pos를 찾으면pos의 왼쪽은 루트 노드의 왼쪽 트리,pos의 오른쪽은 루트 노드의 오른쪽 트리를 각각 역행하면 된다.

public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        TreeNode root = reConstructBinaryTree(pre,in,0,pre.length-1,0,in.length-1);
        return root;
    }
    private TreeNode reConstructBinaryTree(int[] pre,int[] in,int preLeft,int preRight,int inLeft,int inRight){
        if(preLeft > preRight || inLeft > inRight)
            return null;
        TreeNode root = new TreeNode(pre[preLeft]);
        int i;
        for(i = inLeft;i < inRight && in[i] != pre[preLeft];i++);// 
        root.left = reConstructBinaryTree(pre,in,preLeft+1,preLeft+i-inLeft,inLeft,i-1);
        root.right = reConstructBinaryTree(pre,in,i-inLeft+preLeft+1,preRight,i+1,inRight);
        return root;
    }
}

본고는 주로 데이터 구조에서 나무에 관한 지식을 고찰하는데 저는 이 방법만 생각했습니다. 다른 방법이 있다면 토론을 환영합니다.