#include<iostream>
#include<stack>
#include<queue>
#include<stdlib.h>
#include<string>
#include<string.h>
#include<stdio.h>
using namespace std;
template<typename T>
struct node
{
T data;
node *left;
node *right;
};
template<typename T>
node<T> *create(int level)
{
if (!level) return NULL;
node<T> *t = new node<T>();
t->data = rand() % 10; t->left = t->right = NULL;
if (1 == level) return t;
int v = rand() % 3;
switch(v)
{
case 0:
t->left = create<T>(level - 1);
t->right = create<T>(level - 1);
break;
case 1:
t->left = create<T>(level - 1);
break;
case 2:
t->right = create<T>(level - 1);
break;
default: break;
}
return t;
}
template<typename T>
node<T> *build(T *pre, T *mid, int n)
{
if(!pre || !mid || !n) return NULL;
node<T> *t = new node<T>(); t->data = *pre;
t->left = t->right = NULL;
if (1 == n) return t;
T *me = mid - 1;
while (*++me != *pre && me < mid + n);
int llen = me - mid, rlen = n - llen - 1;
if (llen > 0) t->left = build(pre + 1, mid, llen);
if (rlen > 0) t->right = build(pre + llen + 1, mid + llen + 1, rlen);
return t;
}
template<typename T>
void free_tree(node<T> *t)
{
if (!t) return;
free_tree(t->left);
free_tree(t->right);
delete t;
}
template<typename T>
void front_order(const node<T> *t)
{
if (!t) return;
cout << t->data;
front_order(t->left);
front_order(t->right);
}
template<typename T>
void front(node<T> *t)
{
if (!t) return;
stack<node<T> *> s;
while (t || !s.empty())
{
while (t) { cout << t->data; s.push(t); t = t->left;}
t = s.top(); s.pop(); t = t->right;
}
}
template<typename T>
void mid_order(node<T> *t)
{
if (!t) return;
mid_order(t->left);
cout << t->data;
mid_order(t->right);
}
template<typename T>
void mid(node<T> *t)
{
if (!t) return;
stack<node<T> *> s;
while (t || !s.empty())
{
while (t) { s.push(t); t = t->left;}
t = s.top(); s.pop();
cout << t->data;
t = t->right;
}
}
template<typename T>
void back_order(node<T> *t)
{
if (!t) return;
back_order(t->left);
back_order(t->right);
cout << t->data;
}
template<typename T>
void back(node<T> *t)
{
if (!t) return;
stack<node<T> *> s;
node<T> *pre = NULL;
while (t || !s.empty())
{
while (t) { s.push(t); t = t->left;}
t = s.top();
if (t->right == NULL || pre == t->right)
{
cout << t->data;
s.pop(); pre = t; t = NULL;
}
else t = t->right;
}
}
template<typename T>
void level(node<T> *t)
{
if (!t) return;
queue<node<T> *> q;
q.push(t); q.push(NULL);
while (q.size() > 1)
{
t = q.front(); q.pop();
if (NULL == t) { cout << endl; q.push(NULL); continue;}
cout << t->data;
if (t->left) q.push(t->left);
if (t->right) q.push(t->right);
}
}
template<typename T>
node<T> *change_order(node<T> *t)
{
static node<T> *pre = NULL;
static node<T> *head = NULL;
if (!t) return head;
change_order(t->left);
t->left = pre;
pre ? pre->right = t : head = t;
pre = t;
change_order(t->right);
return head;
}
template<typename T>
node<T> *change(node<T> *t)
{
if (!t) return NULL;
node<T> *pre = NULL;
node<T> *head = NULL;
stack<node<T> *> s;
while (t || !s.empty())
{
while (t) {s.push(t); t = t->left;}
t = s.top(); s.pop();
t->left = pre;
pre ? pre->right = t : head = t;
pre = t;
t = t->right;
}
return head;
}
template<typename T>
void print_list(node<T> *t)
{
if (!t) return;
node<T> *p = NULL;
while (t)
{
cout << t->data;
t = t->right;
}
}
template<typename T>
void free_list(node<T> *t)
{
if (!t) return;
node<T> *p = NULL;
while (t)
{
p = t;
t = t->right;
delete p;
}
}
int main(void)
{
char pres[1000];
char mids[1000];
while (scanf("%s %s", pres, mids) != EOF)
{
node<char> *h = build(pres, mids, strlen(pres));
level(h);
back_order(h);
cout << endl;
node<char> *t = change_order(h);
print_list(t);
free_list(t);
}
return 0;
}
/*The second parameter is to store the height of tree.
Initially, we need to pass a pointer to a location with value
as 0. So, function should be used as follows:
int height = 0;
struct node *root = SomeFunctionToMakeTree();
int diameter = diameterOpt(root, &height); */
int diameterOpt(struct node *root, int* height)
{
/* lh --> Height of left subtree
rh --> Height of right subtree */
int lh = 0, rh = 0;
/* ldiameter --> diameter of left subtree
rdiameter --> Diameter of right subtree */
int ldiameter = 0, rdiameter = 0;
if(root == NULL)
{
*height = 0;
return 0; /* diameter is also 0 */
}
/* Get the heights of left and right subtrees in lh and rh
And store the returned values in ldiameter and ldiameter */
ldiameter = diameterOpt(root->left, &lh);
rdiameter = diameterOpt(root->right, &rh);
/* Height of current node is max of heights of left and
right subtrees plus 1*/
*height = max(lh, rh) + 1;
return max(lh + rh + 1, max(ldiameter, rdiameter));
}
Time Complexity: O(n)