leetcode problems

105. Construct Binary Tree from Preorder and Inorder Traversal

Binary Tree reconstruction problem. First comes an example

leet code serialize: 5,1,8,#,3,6,#,2,4,#,7

preorder: 5,1,3,2,4,8,6,7

inorder: 1,2,3,4,5,6,7,8

Strategies.

DP

Considering that we have built tree for the first i-1 nodes comes into preorder list. Now we need to insert ith node into it. We have following conditions:

1. order(inorder(i)) > order(inorder(i-1))
   ith node could be previous node’s right child,
   or it could be the right child of one of the node that has prevous one in its left tree.
   So we need to go upward to see if order of ith node is even larger than such parent. And assign it to right place.
2. order(inorder(i)) < order(inorder(i-1))
   In this case ith node must be i-1th node’s left child, because if there is any other alternative, it must have comed into preorder lsit before ith node.

Division and Conquer

In preorder, parent always comes first, then left sub-tree, finally right sub-tree. So first must be the root, which is 5 in this example. Then all nodes left to 5 in inorder list must be in its left subtree because they comes before 5. So which are right to 5 must be in its right subtree. So this array divided to [1,2,3,4] 5 and [6,7,8]. In [1,2,3,4], the first comes in preorder list is 1, so 1 must be root of this sub-tree. So its divided into [] 1 [2,3,4]. When all problems divided into []. Tree built.

##Implementation.

DP

According to condition 1 in DP, we know that there are possible backtracking. For every node, we need to record the closest parent node that have this node in its left sub-tree and there will be possible update. So We will need to store those Nodes but not just value it stores. So there will be a set of node pair that records such relation. For example:

unordered_map<TreeNode*,TreeNode*>
//or
vector<int> right_parent_index_list
vector<TreeNode*> right_parent_list

Obviously using vector is cheaper than unordered_map when query time are all O(1). But maintaining two array makes coding more complex. What’s more, there are two vectors to be maintained, maitain INT is more expensive than pointer. So using map is better.
Also, preorder list is only used as a dict, if we leave it an array, we total query time will be O(n!). So we also build a hash map for it. Then query time is reduced to O(1).

Here comes pseucode.

For (i = 1:size(preorder) ){
	if(in_order(i) > order(prev)){
		possible_dad = parent_map(prev);
		while(possible_dad != null && in_order(i) > in_order(prev){
			prev = possible_dad;
			possible_dad = prev;
		}
		prev->right = i;
		parent_map(i) = possible_dad;
	}else{
		prev->right = i;
		parent_map(i) = prev;
	}
	prev = i;
}

statistic

• Best time complex O(n)
• Worst time complex O(nlogn)
• space complex O(n)

Division and Conquer

Using recursion is the most direct method. Here comes psudocode. We also need to build a map to make query in inorder list faster.

function(pre_list, in_order, leftbound, rightbound){
	if(leftbound > rightbound) stop;
	m = indexof(max(in_order, leftbound, rightbound));
	root = prelist[m];
	root.left = function(..,..,leftbound, l, m-1);
	root.right = function(..,..,m+1, rightbound);
}

statistic

• time complex O(nlogn)
• space complex O(n)

##Code Record

TreeNode* buildTree(vector<int>& pre, vector<int>& in) {
    if(!pre.size() || !in.size() ) return NULL;
    unordered_map<TreeNode*,TreeNode*> pm;
    unordered_map<int, int> inm;
    TreeNode* pnode;
    for(int i = 0;i < in.size(); ++i){
        inm[in[i]] = i;
    }
    TreeNode* root = new TreeNode(pre[0]);
    pm[root] = nullptr;
    pnode = root;
    for(int i = 1;i < pre.size(); ++i){
        TreeNode* node = new TreeNode(pre[i]);
        if(inm[node->val] > inm[pnode->val]){
            TreeNode* ppnode = pm[pnode];
            while(ppnode != nullptr){
                if(inm[node->val] < inm[ppnode->val]) break;
                pnode = ppnode;
                ppnode = pm[pnode];
            }
            pnode->right = node;
            pm[node] = ppnode;
        }else{
            pnode->left = node;
            pm[node] = pnode;
        }
        pnode = node;
    }
    return root;
}

Similiar problems

• (106) Construct Binary Tree from Inorder and Postorder Traversal
• (109) Convert Sorted List to Binary Search Tree