package com.q0106;
import com.q0101_symmetric_tree.TreeNode;
import java.util.HashMap;
import java.util.Map;


/**
 * @author xjn
 * @since 2020-05-24
 * 106. 从中序与后序遍历序列构造二叉树
 */
public class Solution {
    private Map<Integer, Integer> map = new HashMap<>();
    //中序遍历:左根右
    //后续遍历:左右根
	public TreeNode buildTree(int[] inorder, int[] postorder) {
		if (inorder == null || postorder == null) {
			return null;
		}
		for (int i = 0; i < inorder.length; i++) {
			map.put(inorder[i], i);
		}
		return helper(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
	}
	//中序遍历:左根右
	//后续遍历:左右根
	private TreeNode helper(int[] inorder, int iStart, int iEnd, int[] postorder, int pStart, int pEnd) {
		if (iStart > iEnd || pStart > pEnd) {
			return null;
		}
		//
		TreeNode root = new TreeNode(postorder[pEnd]);
		int rootPos = map.get(postorder[pEnd]);
		int rightNum = iEnd - rootPos;
		root.left = helper(inorder, iStart, rootPos - 1, postorder, pStart, pEnd - rightNum - 1);
		root.right = helper(inorder, rootPos + 1, iEnd, postorder, pEnd - rightNum, pEnd - 1);
		return root;
	}
}