プログラマーの面接の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;
}