LeetCode——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.
原題リンク:https://oj.leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
テーマ:1本の木の前序と中序を遍歴して、1本の二叉木を構築します.
分析:前順遍歴の最初のノードはルートノードであり、このノードは中順遍歴で左右のサブツリーの境界とすることができ、再帰的な遍歴でノード間の依存関係を見つけることができる.

	public TreeNode buildTree(int[] preorder, int[] inorder) {
		return buildTree(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
	}
	
	public TreeNode buildTree(int[] preorder,int startpre,int endpre,int[] inorder,int startin,int endin){
		if(startpre>endpre || startin>endin)
			return null;
		int pivot = preorder[startpre];
		int index = 0;
		for(index=startin;index<=endin;index++){
			if(inorder[index]==pivot)
				break;
		}
		TreeNode root = new TreeNode(pivot);
		root.left = buildTree(preorder,startpre+1,startpre+(index-startin),inorder,startin,index-1);
		root.right = buildTree(preorder,startpre+(index-startin)+1,endpre,inorder,index+1,endin);
		return root;
	}

	// Definition for binary tree
	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}

reference : http://zhangzhenyuan163.blog.163.com/blog/static/8581938920129524612517/