Construct Binary Tree from Preorder and Inorder Traversal 두 갈래 트리 @LeetCode

package Level4;

import Utility.TreeNode;

/**
 * 
 * Construct Binary Tree from Preorder and Inorder Traversal
 * 
 * Given preorder and inorder traversal of a tree, construct the binary tree.
 * 
 * Note: You may assume that duplicates do not exist in the tree.
 * 
 */
public class S140 {

	public static void main(String[] args) {
		int[] preorder = {1};
		int[] inorder = {1};
		buildTree(preorder, inorder);
	}

	public static TreeNode buildTree(int[] preorder, int[] inorder) {
		int len = preorder.length;
		if(len == 0){
			return null;
		}
		return rec(preorder, inorder, 0, len, 0, len);
	}
	
	public static TreeNode rec(int[] preorder, int[] inorder, int preStart, int preEnd, int inStart, int inEnd){
		if(preStart >= preorder.length){		//  ！
			return null;
		}
		TreeNode root = new TreeNode(preorder[preStart]);
		int rootIndex;
		for(rootIndex=inStart; rootIndex<=inEnd; rootIndex++) {
			if(inorder[rootIndex] == preorder[preStart]){	//  inorder root 
				break;
			}
		}
		
		int len = rootIndex - inStart;		//  
		if(rootIndex > inStart){
			root.left = rec(preorder, inorder, preStart+1, preStart+len, inStart, rootIndex-1);
		}
		if(rootIndex < inEnd){
			root.right = rec(preorder, inorder, preStart+len+1, preEnd, rootIndex+1, inEnd);
		}
		
		return root;
	}
	
}

int preIndex = 0;
	
	public TreeNode buildTree(int[] preorder, int[] inorder) {
		return rec(preorder, inorder, 0, inorder.length-1);
	}
	
	public TreeNode rec(int[] preorder, int[] inorder, int inStart, int inEnd) {
		
	    if (inStart > inEnd) {
	        return null;
	    }
	    
	    int rootData = preorder[preIndex++];
	    TreeNode root = new TreeNode(rootData);
	    
	    int inIndex = search(inorder, inStart, inEnd, rootData);
	    
	    root.left = rec(preorder, inorder, inStart, inIndex-1);
	    root.right = rec(preorder, inorder, inIndex+1, inEnd);
	    
	    return root;
	}
	
	private int search(int[] inorder, int inStart, int inEnd, int data) {
	    for(int i=inStart; i<=inEnd; i++) {
	        if(inorder[i] == data) {
	            return i;
	        }
	    }
	    return -1;
	}

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return rec(preorder, inorder, 0, preorder.length-1, 0, inorder.length-1);
    }
    
    public TreeNode rec(int[] preorder, int[] inorder, int preorderLeft, int preorderRight, int inorderLeft, int inorderRight) {
        if(preorderLeft > preorderRight) {
            return null;
        }
        
        TreeNode root = new TreeNode(preorder[preorderLeft]);
        int inorderRootPos = 0;
        for(; inorderRootPos < inorderRight; inorderRootPos++) {
            if(inorder[inorderRootPos] == root.val) {
                break;
            }
        }
        
        int dist = inorderRootPos - inorderLeft;
        root.left = rec(preorder, inorder, preorderLeft+1, preorderLeft+dist, inorderLeft, inorderRootPos-1);
        root.right = rec(preorder, inorder, preorderLeft+dist+1, preorderRight, inorderRootPos+1, inorderRight);
        return root;
    }
}