<검지offer> 출제-[나무] 면접문제 7: 두 갈래 나무 재건

1. 제목 설명:

2. 문제 풀이 사고방식:

3. 코드 구현:

1. 제목 설명:

 ， 。 。 
 {1,2,4,7,3,5,6,8} {4,7,2,1,5,3,8,6}， 。

2. 문제 풀이 사고방식:

두 갈래 나무의 앞 순서가 두루 돌아다니는 동안 첫 번째 숫자는 항상 나무의 뿌리 노드이다.중간 순서에서 트리의 루트 노드는 서열의 중간에 있고 왼쪽 트리의 노드는 루트 노드의 왼쪽에 있고 오른쪽 트리 노드의 값은 루트 노드의 오른쪽에 있습니다.
따라서 스캔 중인 트리 노드의 개수와 오른쪽 트리 노드의 개수를 찾을 수 있습니다. 그리고 앞 트리 노드에서 왼쪽 트리의 루트 노드를 찾은 다음 중간 트리의 왼쪽 트리와 오른쪽 트리를 찾을 수 있습니다.차례로 돌아가다.

3. 코드 구현:

/**
 * 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==null|| in==null || pre.length==0|| in.length)
         //   return null;
        if(pre == null || in == null || pre.length == 0 || in.length == 0){
            return null;
        }
        return buildTree(pre, in, 0, pre.length-1, 0, in.length-1);
    }
        
        // 
     public TreeNode buildTree(int[] pre, int[] in, int preStart, int preEnd, int inStart, int inEnd){
            // ， 
         TreeNode root = new TreeNode(pre[preStart]);
            // ， gen 
         int gen = 0;
         for(int i=0;i<in.length;i++){
             if(in[i]==root.val){
                 gen = i;
                 break;
              }     
          }
          int leftLen = gen-inStart;// 
          int rightLen = inEnd-gen;// 
            // 
          if(leftLen>0)
              root.left = buildTree(pre, in, preStart+1, preStart+leftLen, inStart, gen-1);
            // 
          if(rightLen>0)
              root.right = buildTree(pre, in, preStart+leftLen+1, preEnd, gen+1, inEnd);  
          return root;
      }
}