CareerCup

Node *traversalToTree( int preorder[], int inorder[], int n )
{
	Node *head = NULL;

	for( int i = 0; i < n; i++ )
		head = insert( head, preorder[i], inorder );

	return head;
}

int mycmp( int value1, int value2, int inorder[] )
{
	int pos1 = -1;
	int pos2 = -1;
	int i = 0;

	while( ( pos1 == -1 ) || ( pos2 == -1 ) )
	{
		if( inorder[i] == value1 )
			pos1 = i;

		if( inorder[i] == value2 )
			pos2 = i;

		i++;
	}

	return (pos1-pos2);
}

Node *insert( Node *head, int value, int inorder[] )
{
	Node *pNewNode = new Node();
	pNewNode->value = value;
	pNewNode->left = NULL;
	pNewNode->right = NULL;

	if( head == NULL )
		return pNewNode;

	Node *p = head;
	while( true )
	{
		int compare = mycmp( value, p->value, inorder );
		if( compare <= 0 )
		{
			if( p->left == NULL )
			{
				p->left = pNewNode;
				break;
			}
			else
				p = p->left;
		}
		else
		{
			if( p->right == NULL )
			{
				p->right = pNewNode;
				break;
			}
			else
				p = p->right;
		}
	}

	return head;
}

int pre_index = -1;
Node* in_pre_to_tree(int in[], int pre[], int in_start, int in_end)
{
pre_index++;
Node *root = new Node;
root->data = pre[pre_index];

int i;
for(i = in_start; i <= in_end && in[i] != pre[pre_index]; i++);

if(i == in_start)
root->left = NULL;
else
root->left = in_pre_to_tree(in, pre, in_start, i-1);

if(i == in_end)
root->right = NULL;
else
root->right = in_pre_to_tree(in, pre, i+1, in_end);

return root;
}
output:

On C++

node_t * tree_iter(const std::string &inorder, std::string preorder)
{
    if (inorder.empty() || preorder.empty())
        return 0;

    struct item_t
    {
        node_t **node;
        std::string inorder;
    };

    std::stack<item_t> todo;

    node_t *ret = 0;
    item_t root;
    root.inorder = inorder;
    root.node = &ret;

    todo.push(root);

    while (!todo.empty())
    {
        item_t cur = todo.top();
        todo.pop();

        *cur.node = 0;

        if (cur.inorder.empty() || preorder.empty())
            continue;

        *cur.node = new node_t;

        (*cur.node)->val = preorder[0];
        preorder = preorder.substr(1, preorder.size() - 1);
        size_t pos = cur.inorder.find((*cur.node)->val);
        assert(std::string::npos != pos);

        item_t right;
        right.node = &((*cur.node)->right);
        right.inorder = cur.inorder.substr(pos + 1, cur.inorder.size() - pos - 1);
        todo.push(right);

        item_t left;
        left.node = &((*cur.node)->left);
        left.inorder = cur.inorder.substr(0, pos);
        todo.push(left);
    }

    return ret;
}

Have no idea what question is.

A bit wordy, but it works.

public static TreeNode<Integer> nonRecursReverseTree(Integer[] inOrder, Integer[] preOrder) {

        final Stack<TreeNode<Integer>> treeStack = new Stack<TreeNode<Integer>>();
        final Stack<Bound> bounds = new Stack<Bound>();


        TreeNode<Integer> prevNode = new TreeNode<Integer>(preOrder[0]);
        final TreeNode<Integer> result = prevNode;
        int nodePos = Arrays.binarySearch(inOrder, 0, preOrder.length, preOrder[0]);
        Bound prevBound = new Bound(0, nodePos, preOrder.length);
        treeStack.push(prevNode);
        bounds.push(prevBound);
        int cnt = 2;
        int prePosition = 1;
        while (prePosition < preOrder.length) {
            nodePos = Arrays.binarySearch(inOrder, prevBound.start, prevBound.end, preOrder[prePosition]);
            cnt++;
            if (nodePos >= 0) {
                final TreeNode<Integer> curNode = new TreeNode<Integer>(preOrder[prePosition]);
                final Bound curBound;
                if (prevBound.inTheLeft(nodePos)) {
                    prevNode.left = curNode;
                    curBound = new Bound(prevBound.start, nodePos, prevBound.center);
                } else {
                    prevNode.right = curNode;
                    curBound = new Bound(prevBound.center, nodePos, prevBound.end);
                }
                if (prevBound.onTheLeft(nodePos)) {
                    prevBound = bounds.pop();
                    prevNode = treeStack.pop();
                } else {
                    treeStack.push(curNode);
                    bounds.push(curBound);
                    prevBound = curBound;
                    prevNode = curNode;
                }
                prePosition++;
            } else {
                prevBound = bounds.pop();
                prevNode = treeStack.pop();
            }
        }
        System.out.println("cnt = " + cnt);
        return result;
    }

can we form the tree using a pre-order and post-order traversal without inorder traversal?

int pre_index = -1;
Node* in_pre_to_tree(int in[], int pre[], int in_start, int in_end)
{
	pre_index++;
	Node *root = new Node;
	root->data = pre[pre_index];
	
	int i;
	for(i = in_start; i <= in_end && in[i] != pre[pre_index]; i++);
	
	if(i == in_start)
		root->left = NULL;
	else
		root->left = in_pre_to_tree(in, pre, in_start, i-1);
		
	if(i == in_end)
		root->right = NULL;
	else
		root->right = in_pre_to_tree(in, pre, i+1, in_end);
	
	return root;
}

We can use the preorder and inorder traversal of the tree. More specifically, the preorder has the root of the tree as its first node. We can search this node in the inorder traversal. All nodes to the left of the root in the inorder traversal belong to the root's left subtree and all the nodes to its right fall under the root's right subtree. Recursive calls of the function on these subtrees give us the original tree.