[数据结构与算法]层序构建二叉树后求其深度

【问题描述】
输入二叉树的层序遍历序列（空子树用?#?补全），求二叉树的深度。

【测试样例】
层序构建二叉树的测试样例序列分别为【8 3 2 # # 6 4 # # # #】，【D A # R # E # # N # #】，对应的图分别如下所示：?

【算法分析】
二叉树的问题一般会用递归的思想去考虑，因为二叉树是递归的结构。
此题的关键是层序构建二叉树的代码。
输入样例后，回车。按?Ctrl+Z?输出结果。

【算法代码】

#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

int treeDepth(TreeNode* root) {
	if(root==NULL) return 0;
	return max(treeDepth(root->left), treeDepth(root->right)) + 1;
}

//Create binarytree based on level travelsal
TreeNode* CreateTreeByLevel(vector<char> v) {
	int len=v.size();
	if(len==0) return NULL;

	queue<TreeNode*> queue;

	int index=0;
	TreeNode *root=new TreeNode(v[index++]); //Create root node

	queue.push(root); //Enqueue
	TreeNode *p=NULL;
	while(!queue.empty() && index<len) {
		p=queue.front();
		queue.pop(); //Dequeue

		//Left node
		if(index<len && v[index]!='#') {//Create a node if it isn't empty
			TreeNode *leftNode = new TreeNode(v[index]);
			p->left = leftNode;
			queue.push(leftNode);
		}
		index++;

		//Right node
		if(index<len && v[index]!='#') {//Create a node if it isn't empty
			TreeNode *rightNode = new TreeNode(v[index]);
			p->right = rightNode;
			queue.push(rightNode);
		}
		index++;
	}
	return root;
}

int main() {
	vector<char> s;

	char x;
	while(cin>>x) {
		s.push_back(x);
	}

	cout<<treeDepth(CreateTreeByLevel(s));

	return 0;
}



/*
in1:
8 3 2 # # 6 4 # # # #
out1:
3

in2:
D A # R # E # # N # #
out2:
5
*/

【参考文献】
http://www.bubuko.com/infodetail-551967.html
https://www.acwing.com/problem/content/67/




?