ylf951
BAN USERAssume the binary tree node structure as follows:
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
Use pair<column, depth> as key in multimap.
Here column of a node is defined recursively as:
1) Column of root node is 0;
2) Column of left child of one's node equals its column - 1, column of right child equals its column + 1.
Depth of a node is defined recursively as:
1) For root node, depth is 0;
2) For other nodes, depth is their parent's depth + 1;
class Key
{
public:
Key(int c, int d):column(c), depth(d){}
bool operator<(const Key& k) const
{
if(column == k.column)
return depth < k.depth;
return column < k.column;
}
public:
int column;
int depth;
};
//C++ solution
class Solution {
public:
void printInColumn(TreeNode *T)
{
multimap<Key, int> m;
traverseTree(0, 0, T, m);
multimap<Key, int>::iterator iter = m.begin();
for(; iter != m.end(); iter++)
cout<<iter->second<<" ";
cout<<endl;
}
void traverseTree(int column, int depth, TreeNode *T, multimap<Key, int> &m)
{
if(T != NULL)
{
m.insert(make_pair(Key(column, depth), T->val));
traverseTree(column-1, depth+1, T->left, m);
traverseTree(column+1, depth+1, T->right, m);
}
}
};
Space complexity: O(n)
Time complexity: O(n log (n))
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Key
{
public:
Key(int c, int d):column(c), depth(d){}
bool operator<(const Key& k) const
{
if(column == k.column)
return depth < k.depth;
return column < k.column;
}
public:
int column;
int depth;
};
class Solution {
public:
void printInColumn(TreeNode *T)
{
multimap<Key, int> m;
traverseTree(0, 0, T, m);
multimap<Key, int>::iterator iter = m.begin();
for(; iter != m.end(); iter++)
cout<<iter->second<<" ";
cout<<endl;
}
void traverseTree(int depth, int column, TreeNode *T, multimap<Key, int> &m)
{
if(T != NULL)
{
m.insert(make_pair(Key(column, depth), T->val));
traverseTree(depth+1, column-1, T->left, m);
traverseTree(depth+1, column+1, T->right, m);
}
}
};
C++ solution
- ylf951 March 14, 2016