Originally Posted by
Buster Highmen
#include<bits/stdc++.h>
using namespace std;
class Node {
public:
int data;
Node *left;
Node *right;
Node(int d) {
data = d;
left = NULL;
right = NULL;
}
};
class Solution {
public:
Node* insert(Node* root, int data) {
if(root == NULL) {
return new Node(data);
} else {
Node* cur;
if(data <= root->data) {
cur = insert(root->left, data);
root->left = cur;
} else {
cur = insert(root->right, data);
root->right = cur;
}
return root;
}
}
/*
class Node {
public:
int data;
Node *left;
Node *right;
Node(int d) {
data = d;
left = NULL;
right = NULL;
}
};
*/
/////////////////////////////////////////////////////////////////////////////////////////////////
// Each node in the binary tree has a unique level(height) and column. The goal is to print out the data
// for each column at the lowest level. These are the "visible" nodes if the tree is viewed from the top.
//
// The idea is to walk the tree and store the following information.
// Whenever for a given column, the level (height) is less, overwrite the fields at that
// column index.
//
typedef struct __NODE_INFO {
int m_NodeData;
int m_NodeColumn;
int m_NodeLevel;
} NODE_INFO, *PNODE_INFO;
#define NUMBER_OF_DATA_NODES 1002
#define MIDDLE_OF_DATA_NODES (NUMBER_OF_DATA_NODES/2)
NODE_INFO gDataNodes[NUMBER_OF_DATA_NODES];
// These makes for nice optimizations when dumping the resulting array.
//
int gLeftMostColumn = 0;
int gRightMostColumn = 0;
// Do an Inorder walk of the tree, conditionally filling gDataNodes and
// keeping track of the levels and columns of each node in the tree.
//
void
topViewLevel(
Node * node,
int level,
int column
)
{
++level;
if (node->left)
{
// Keep track of the column in the recursion
//
--column;
// Store the leftMostcolumn to optimize search later.
//
if (column < gLeftMostColumn)
{
gLeftMostColumn = column;
}
topViewLevel(node->left, level, column);
// Recover the column from recursion.
//
++column;
}
// The arrays m_NodeLevels are initialized to a max level of 500.
// If for a given column, the current level is less than the one stored in the array,
// overwrite the level and data in the array.
//
if (gDataNodes[MIDDLE_OF_DATA_NODES + column].m_NodeLevel > level )
{
gDataNodes[MIDDLE_OF_DATA_NODES + column].m_NodeLevel = level;
gDataNodes[MIDDLE_OF_DATA_NODES + column].m_NodeData = node->data;
}
if (node->right)
{
// Track the column for the recursion.
//
++column;
// Optimize the search.
//
if (column > gRightMostColumn)
{
gRightMostColumn = column;
}
// Recurse right.
//
topViewLevel(node->right, level, column);
}
}
void
DumpNodeInfo(
PNODE_INFO NodeInfo
)
{
int i;
for (i = gLeftMostColumn + MIDDLE_OF_DATA_NODES ;
i <= gRightMostColumn + MIDDLE_OF_DATA_NODES;
++i)
{
if (0 != NodeInfo[i].m_NodeData)
{
printf("%d ", NodeInfo[i].m_NodeData);
}
}
}
void
topView(
Node * root
)
{
int i;
// Initialize the array of NODE_INFOs
//
memset(gDataNodes, 0, sizeof(NODE_INFO)*NUMBER_OF_DATA_NODES);
for (i = 0; i < NUMBER_OF_DATA_NODES;++i)
{
gDataNodes[i].m_NodeLevel = 500;
}
// Walk the tree filling gDataNodes.
//
if (NULL != root)
{
topViewLevel(root, 0, 0);
}
// Output the nontrivial contents of gDataInfo.
//
DumpNodeInfo(gDataNodes);
}
}; //End of Solution
