52.二元树的深度。
题目:输入一棵二元树的根结点,求该树的深度。
从根结点到叶结点依次经过的结点(含根、 叶结点)形成树的一条路径,最长路径的长度为
树的深度。
例如:输入二元树:
10
/ \
6 14
/ / \
4 12 16
输出该树的深度 3。
/* 52.二元树的深度。 题目:输入一棵二元树的根结点,求该树的深度。 从根结点到叶结点依次经过的结点(含根、 叶结点)形成树的一条路径,最长路径的长度为 树的深度。 例如:输入二元树: 10 / \ 6 14 / / \ 4 12 16 输出该树的深度 3。 */ #include<iostream> #include<stdio.h> #include<stdlib.h> using namespace std; struct BTreeNode{ int data; BTreeNode *left,*right; }; //建立二叉树 BTreeNode * CreateTree(int data[],int pos,int len) { BTreeNode *tree; if(pos>=len) { return NULL; } else { tree=(BTreeNode *)malloc(sizeof(BTreeNode)); tree->data=data[pos]; tree->left=CreateTree(data,2*pos+1,len);//数组坐标 tree->right=CreateTree(data,2*pos+2,len); return tree; } } //最大深度 int getMaxDepth(BTreeNode *root) { if(root==NULL) return 0; if(NULL==root->left&&NULL==root->right) return 0; int nLeftDepth=0,nRightDepth=0; if(NULL!=root->left) nLeftDepth=getMaxDepth(root->left)+1; if(NULL!=root->right) nRightDepth=getMaxDepth(root->right)+1; return nRightDepth>=nLeftDepth?nRightDepth:nLeftDepth; } int main() { /* 5 4 8 7 12 10 */ int data[]={5,4,8,7,12,10}; int len=sizeof(data)/sizeof(int); BTreeNode *tree=CreateTree(data,0,len); int nMaxDep=getMaxDepth(tree)+1; //求的是根左右的最大深度,根本来就是1 cout <<"求二叉树中节点的深度:"<<nMaxDep<<endl; //3 /* 5 4 8 7 12 10 13 16 */ int data2[]={5,4,8,7,12,10,13,16}; int len2=sizeof(data2)/sizeof(int); BTreeNode *tree2=CreateTree(data2,0,len2); int nMaxDep2 = getMaxDepth(tree2)+1; cout <<"求二叉树中节点的最大深度:"<<nMaxDep2<<endl; //4 return 0; }