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.

确定中序遍历中根节点位置，递归构造左右子树

代码

public class ConstructBinaryTreeFromPreorderAndInorderTraversal {
	public TreeNode buildTree(int[] preorder, int[] inorder) {
		return solve(preorder, 0, inorder, 0, inorder.length - 1);
	}

	private TreeNode solve(int[] preorder, int p, int[] inorder, int low,
			int high) {
		if (low > high) {
			return null;
		}
		TreeNode root = new TreeNode(preorder[p]);
		int cutPos = 0;
		for (int i = low; i <= high; ++i) {
			if (preorder[p] == inorder[i]) {
				cutPos = i;
				break;
			}
		}
		root.left = solve(preorder, p + 1, inorder, low, cutPos - 1);
		root.right = solve(preorder, p + cutPos - low + 1, inorder, cutPos + 1,
				high);
		return root;
	}
}