Google Interview Question
Software EngineersCountry: United States
Interview Type: Phone Interview
public class NArrTreeTraversalModified {
private static class NArrTreeNodeModified {
int val;
ArrayList<NArrTreeNode> children;
boolean canVisit;
public NArrTreeNode(int value) {
val = value;
children = new ArrayList<>();
}
}
public ArrayList<Integer> postOrderTraversal(NArrTreeNodeModified root) {
ArrayList<Integer> result = new ArrayList<>();
Stack<NArrTreeNodeModified> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
NArrTreeNodeModified node = stack.peek();
if (node.children.size() == 0 || node.canVisit) result.add(stack.pop().val);
else {
node.children.forEach(n -> stack.push(n));
node.canVisit = true;
}
}
return result;
}
}
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
struct node
{
int data;
int noc;
node **child;
};
node *getDummyNode()
{
node *N=new node;
N->data=-1;
return N;
}
void printPostOrder(node *T)
{
stack<node *> s1,s2;
s1.push(T);
while(!s1.empty())
{
node *N=s1.top();
if(N->data==-1)
{
s1.pop();
cout<<s2.top()->data<<" ";
s2.pop();
}
else
{
s2.push(N);
s1.pop();
s1.push(getDummyNode());
int s=N->noc;
for(int i=s-1;i>=0;i--)
{
s1.push(N->child[i]);
}
}
}
}
node *getNode(int k,int noc)
{
node *N=new node;
N->data=k;
N->noc=noc;
N->child=new node*[noc];
for(int i=0;i<noc;i++)
{
N->child[i]=NULL;
}
return N;
}
int main()
{
node *T=NULL;
T=getNode(1,3);
T->child[0]=getNode(2,3);
T->child[1]=getNode(3,4);
T->child[2]=getNode(4,0);
T->child[0]->child[0]=getNode(5,0);
T->child[0]->child[1]=getNode(6,0);
T->child[0]->child[2]=getNode(7,0);
T->child[1]->child[0]=getNode(8,0);
T->child[1]->child[1]=getNode(9,0);
T->child[1]->child[2]=getNode(10,0);
T->child[1]->child[3]=getNode(11,0);
printPostOrder(T);
}
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
struct node
{
int data;
int noc;
node **child;
};
node *getDummyNode()
{
node *N=new node;
N->data=-1;
return N;
}
void printPostOrder(node *T)
{
stack<node *> s1,s2;
s1.push(T);
while(!s1.empty())
{
node *N=s1.top();
if(N->data==-1)
{
s1.pop();
cout<<s2.top()->data<<" ";
s2.pop();
}
else
{
s2.push(N);
s1.pop();
s1.push(getDummyNode());
int s=N->noc;
for(int i=s-1;i>=0;i--)
{
s1.push(N->child[i]);
}
}
}
}
node *getNode(int k,int noc)
{
node *N=new node;
N->data=k;
N->noc=noc;
N->child=new node*[noc];
for(int i=0;i<noc;i++)
{
N->child[i]=NULL;
}
return N;
}
int main()
{
node *T=NULL;
T=getNode(1,3);
T->child[0]=getNode(2,3);
T->child[1]=getNode(3,4);
T->child[2]=getNode(4,0);
T->child[0]->child[0]=getNode(5,0);
T->child[0]->child[1]=getNode(6,0);
T->child[0]->child[2]=getNode(7,0);
T->child[1]->child[0]=getNode(8,0);
T->child[1]->child[1]=getNode(9,0);
T->child[1]->child[2]=getNode(10,0);
T->child[1]->child[3]=getNode(11,0);
printPostOrder(T);
}
struct Node {
int val;
int index;
vector<Node*> children;
};
void createTree(Node *head)
{
Node *node, *qNode;
char ch;
queue<Node *> q;
cout << "Enter value of head node: ";
cin >> head->val;
head->index = 0;
q.push(head);
while (!q.empty())
{
qNode = q.front();
q.pop();
cout << "do you want to add child of " << qNode->val << "?" << endl;
cin >> ch;
while (ch == 'y' || ch == 'Y')
{
node = new Node();
cout << "Enter value of head node: ";
cin >> node->val;
node->index = 0;
qNode->children.push_back(node);
q.push(node);
cout << "do you want to add another child of " << qNode->val << "?" << endl;
cin >> ch;
}
}
}
//Recursive solution
void postorderRec(Node *head)
{
if (head == NULL)
{
cout << "empty tree" << endl;
return;
}
if (head->children.empty())
cout << head->val << " ";
else
{
for (vector<Node *>::iterator iter = head->children.begin(); iter != head->children.end(); iter++)
{
postorderRec(*iter);
}
cout << head->val << " ";
}
}
//Iterative solution
void postorderiTer(Node *node)
{
if (node == NULL)
{
cout << "empty tree" << endl;
return;
}
stack <Node *>st;
Node *temp;
st.push(node);
while (!st.empty())
{
temp = st.top();
if (temp->index < temp->children.size())
{
node = temp->children[temp->index];
temp->index++;
st.push(node);
}
else
{
st.pop();
cout << temp->val << " ";
}
}
}
int main()
{
Node *head = new Node();
createTree(head);
postorderRec(head);
cout << endl;
postorderiTer(head);
return 0;
}
- jiangok2006 September 14, 2015