プログラマーの面接の100題(アルゴリズム)の再帰は二叉木の深さを求めます
1346 ワード
// 100 ( )
#include "stdafx.h"
#include <iostream>
#include <deque>
using namespace std;
struct BiTreeNode
{
BiTreeNode *leftNode;
BiTreeNode *rightNode;
int value;
};
BiTreeNode *CreateBiTree(BiTreeNode *&root)
{
int data = 0;
cin >> data;
if(-1 == data)
return NULL;
else
{
root= (BiTreeNode*)malloc(sizeof(BiTreeNode));
if(root)
{
root->value = data;
root->leftNode = NULL;
root->rightNode = NULL;
CreateBiTree(root->leftNode);
CreateBiTree(root->rightNode);
}
else
{
cout << "No space" <<endl;
return NULL;
}
}
return root;
}
int TreeDepth(BiTreeNode *root)
{
// the depth of a empty tree is 0
if(!root)
return 0;
// the depth of left sub-tree
int nLeft = TreeDepth(root->leftNode);
// the depth of right sub-tree
int nRight = TreeDepth(root->rightNode);
// depth is the binary tree
return (nLeft > nRight) ? (nLeft + 1) : (nRight + 1);
}
int _tmain(int argc, _TCHAR* argv[])
{
BiTreeNode *root = NULL;
cout << "Please create the tree with preorder(-1 means NULL):" << endl;
CreateBiTree(root);
cout << "Depth of tree is:" << endl;
cout << TreeDepth(root) << endl;
return 0;
}