package com.q0105;

import com.q0104_maximum_depth_of_binary_tree.TreeNode;

/***
 * https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
 * 前序遍历 preorder = [3,9,20,15,7]
 * 中序遍历 inorder = [9,3,15,20,7]
 */
public class Solution {
	public TreeNode buildTree(int[] preorder, int[] inorder) {
		if (preorder == null || inorder == null) {
			return null;
		}
		return dfs(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
	}

	private TreeNode dfs(int[] preorder, int pStart, int pEnd, int[] inorder, int iStart, int iEnd) {
		//pStart可以等于pEnd
		if (pStart > pEnd || iStart > iEnd) {
			return null;
		}
		TreeNode root = new TreeNode(preorder[pStart]);
		int step = 0;
		while (preorder[pStart] != inorder[iStart + step]) {
			step++;
		}
		//前序:根左右
		//中序:左根右
		root.left = dfs(preorder, pStart + 1, pEnd, inorder, iStart, iStart + step - 1);
		root.right = dfs(preorder, pStart + step + 1, pEnd, inorder, iStart + step + 1, pEnd);
		return root;
	}

}