[LeetCode]Construct Binary Tree from Inorder and Preorder Traversal

Preorder 最左边的的就是当前 Tree 或者 Subtree 的 root，所以我们用 inorder 里 root 的位置来分 subtree，分开的两个区域的最左边就是当前 subtree 的 root，我们递归地进行这个步骤。
如果每次都在 array 里扫当前 subtree root 的位置的话，时间复杂度 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[] preorder, int[] inorder) {
	int len = preorder.length;
	return buildSubtree(preorder, 0, len - 1, inorder, 0, len - 1);
	}
	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;
	}
	private TreeNode buildSubtree(int[] preorder, int lo1, int hi1, int[] inorder, int lo2, int hi2) {
	if (lo2 > hi2)
	return null;
	TreeNode node = new TreeNode(preorder[lo1]);
	int index = find(inorder, preorder[lo1], lo2, hi2);
	int leftLen = index - lo2;
	int rightLen = hi2 - index;
	node.left = buildSubtree(preorder, lo1 + 1, lo1 + leftLen, inorder, lo2, index - 1);
	node.right = buildSubtree(preorder, lo1 + leftLen + 1, lo1 + leftLen + rightLen, inorder, index + 1, hi2);
	return node;
	}
	}

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

如果我们用 map 来记录所有元素的位置的话，时间复杂度 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[] preorder, int[] inorder) {
	if (preorder == null || inorder == null)
	return null;
	if (preorder.length != inorder.length)
	return null;
	int len = inorder.length;
	HashMap<Integer, Integer> inorderMap = new HashMap<Integer, Integer>();
	for (int i = 0; i < len; i++)
	inorderMap.put(inorder[i], i);
	return build(preorder, 0, len - 1, inorder, 0, len - 1, inorderMap);
	}
	private TreeNode build(int[] preorder, int lo1, int hi1, int[] inorder, int lo2, int hi2, HashMap<Integer, Integer> inorderMap) {
	if (lo2 > hi2)
	return null;
	TreeNode node = new TreeNode(preorder[lo1]);
	int inorderIndex = inorderMap.get(preorder[lo1]);
	int left = inorderIndex - lo2, right = hi2 - inorderIndex;
	node.left = build(preorder, lo1 + 1, lo1 + left, inorder, lo2, inorderIndex - 1, inorderMap);
	node.right = build(preorder, lo1 + left + 1, hi1, inorder, inorderIndex + 1, hi2, inorderMap);
	return node;
	}
	}

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

另外我们也可以用iterative的做法，我们之前做过iterative前序遍历二叉树的题，这道题我们可以采用类似的思路。我们知道preorder是按照[root][left-subtree][right-subtree]的格式来表示每一个子树的，问题的关键就在于如何从叶节点或者左子树已经被遍历的节点跳转到对应的后继节点。在上面链接的题目当中我们是用stack来解决这个问题的，这里我们依然需要用stack。但是单纯地依靠前序遍历的序列也是不够，这时候我们就需要中序的序列来帮助解决这个问题。当我们从左到右遍历到中序序列的某一个元素时，要么当前元素时叶节点，要么左子树已经遍历完了，所以当前序序列的当前元素和中序序列当前元素相等的时候，我们知道应该去找后继节点了，我们pop栈顶的元素，这里有两种情况：

• 当前元素没有右子树，这样的话pop之后的栈顶元素和中序序列的下一个元素还是一样的，因为没有右子树的情况下，左子结点的后继结点就是父节点，我们继续pop
• 当前元素有右子树，这时候栈顶元素和中序的下一个元素不相等。因为我们遍历完了左子树，前序序列的下一个元素就是其右子结点

否则的话前序序列的下一个数一定是前一个数的左子结点。时间复杂度，空间复杂度均为O(n)，代码如下：

	/**
	* Definition for a binary tree node.
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Solution {
	public:
	TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
	if (preorder.size() != inorder.size())return nullptr;
	int len = preorder.size(), i = 0, j = 0;
	stack<TreeNode*> st;
	TreeNode* res = nullptr;
	bool isLeft = true;
	while (i < len)
	{
	TreeNode* root = st.size()? st.top(): nullptr;
	while (st.size() && st.top()->val == inorder[j])
	{
	root = st.top();
	st.pop();
	++j;
	isLeft = false;
	}
	TreeNode* node = new TreeNode(preorder[i]);
	if (!res)res = node;
	if (root)
	{
	if (isLeft)root->left = node;
	else { root->right = node; isLeft = true; }
	}
	st.push(node);
	++i;
	}
	return res;
	}
	};

view raw Construct Binary Tree from Preorder and Inorder Traversal.cpp hosted with ❤ by GitHub