程序员面试100题(算法)之递归求二叉树深度
// 程序员面试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;}