given binary tree inorder & preorder traversal, return postorder traversal

Question

anarchotroll · Accepted Answer

Just implemented this in javascript on the browser (out of pure laziness). 

Here's some explanation: The first element on the "preorder" list will always be the root. 
1. Find that element in the inorder list and split it. 
2. Pop the element from the pre-order list. There you go, just apply recursion now. The following element on the pre-order list will be the new root of either "leftList" or "rightList" (if leftList is empty). Just recursively apply this algorithm on the new lists.


function postOrder(preOrder, inOrder, result) {
	var root = preOrder[0];
	var splitArray;
	var rootIndexInOrder;
	var leftElements;
	var rightElements;
	preOrder.splice(0,1);

	for(var i = 0; i < inOrder.length; ++i) {

		if(inOrder[i] === root) {
			rootIndexInOrder = i;
			break;
		}
	}

	leftElements = inOrder.slice(0, rootIndexInOrder);
	rightElements = inOrder.slice(rootIndexInOrder+1);

	if(leftElements.length !== 0) {
		postOrder(preOrder, leftElements, result);
	}
	
	if(rightElements.length !== 0) {
		postOrder(preOrder, rightElements, result);
	}

	result.push(root);
	
}

Anonimo · Answer

recursion

Microsoft

Domanda di colloquio di Microsoft

Risposte di colloquio

Aziende seguite

Ricerche di lavoro