[LeetCode]Construct Binary Tree from Inorder and Postorder Traversal

和 Construct Binary Tree from Inorder and Postorder Traversal 是类似的。

O(n log n):

	/**
	* 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[] inorder, int[] postorder) {
	int len = inorder.length;
	return buildSubtree(inorder, 0, len - 1, postorder, 0, len - 1);
	}
	private TreeNode buildSubtree(int[] inorder, int lo1, int hi1, int[] postorder, int lo2, int hi2){
	if (lo1 > hi1)
	return null;
	TreeNode node = new TreeNode(postorder[hi2]);
	int index = find(inorder,postorder[hi2], lo1, hi1);
	int leftLen = index - lo1;
	int rightLen = hi1 - index;
	node.left = buildSubtree(inorder, lo1, index - 1, postorder, lo2, lo2 + leftLen - 1);
	node.right = buildSubtree(inorder, index + 1, hi1, postorder, hi2 - rightLen, hi2 - 1);
	return node;
	}
	private int find(int[] inorder, int target, int lo, int hi){
	for (int i = lo; i <= hi; i++){
	if (inorder[i] == target)
	return i;
	}
	return -1;
	}
	}

view raw construct bst from in order and postorder traversal v-1.java hosted with ❤ by GitHub

O(n)：

	/**
	* 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[] inorder, int[] postorder) {
	if (inorder == null || postorder == null)
	return null;
	if (inorder.length != postorder.length)
	return null;
	int len = inorder.length;
	HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
	for (int i = 0; i < len; i++)
	map.put(inorder[i], i);
	return buildTree(inorder, 0, len - 1, postorder, 0, len - 1, map);
	}
	private TreeNode buildTree(int[] inorder, int lo1, int hi1, int[] postorder, int lo2, int hi2, HashMap<Integer, Integer> map) {
	if (lo1 > hi1)
	return null;
	TreeNode node = new TreeNode(postorder[hi2]);
	int index = map.get(postorder[hi2]);
	int left = index - lo1, right = hi1 - index;
	node.left = buildTree(inorder, lo1, index - 1, postorder, lo2, lo2 + left - 1, map);
	node.right = buildTree(inorder, index + 1, hi1, postorder, lo2 + left, hi2 - 1, map);
	return node;
	}
	}

view raw construct bst from in order and postorder traversal v-2.java hosted with ❤ by GitHub