FactSet Research Systems, Inc Interview Question
Software Engineer / Developerspublic int maxDepthIter() {
if (root == null)
return 0;
Queue<Node> q = new LinkedList<Node>();
int max_depth = 0, depth = 0;
q.add(root);
depth++;
while(!q.isEmpty()) {
int count = q.size();
for (int i = 0; i < count; i++) {
Node n = q.remove();
if (n.left == null && n.right == null) {
if(max_depth < depth)
max_depth = depth;
continue;
}
if (n.left != null)
q.add(n.left);
if (n.right != null)
q.add(n.right);
}
depth++;
}
return max_depth;
}
a c++ solution
#include <iostream>
#include <utility>
#include <queue>
using namespace std;
struct TreeNode{
int val;
TreeNode *left, *right;
TreeNode(int x):val(x){}
};
int maxDepth(TreeNode *root){
if(!root)
return 0;
return 1+max(maxDepth(root->left),maxDepth(root->right));
}
int maxDepth1(TreeNode *root){
if(!root)
return 0;
queue<pair<TreeNode *,int> > to_process;
to_process.push(make_pair(root,1));
int max_depth=1;
while(!to_process.empty()){
pair<TreeNode*,int> cur = to_process.front();
to_process.pop();
max_depth=max(max_depth,cur.second);
if(cur.first->left)
to_process.push(make_pair(cur.first->left,cur.second+1));
if(cur.first->right)
to_process.push(make_pair(cur.first->right,cur.second+1));
}
return max_depth;
}
int main(void){
TreeNode *root=new TreeNode(0);
root->left=new TreeNode(0);
root->left->left=new TreeNode(0);
root->left->left->left=new TreeNode(0);
root->right=new TreeNode(0);
root->right->left=new TreeNode(0);
cout<<maxDepth(root)<<maxDepth1(root)<<endl;
cout<<maxDepth(root->right)<<maxDepth1(root->right)<<endl;
return 0;
}
global variable maxdepth = 0;
- xinthe September 04, 2007void findMaxDepth()
{
MaxDepth(root, -1);
}
void find MaxDepth(class node *ptrNode, int depth)
{
if(ptrNode == null) {return;}
depth++;
if(maxDepth < depth)
{
maxDepth = depth;
}
if(ptrNode->Left!=null)
{
MaxDepth(ptrNode->left, depth);
}
if(ptrNode->Right!=null)
{
MaxDepth(ptrNode->Right, depth);
}
}