[二叉树] 求二叉树的高度（递归与非递归两种方法）

• 利用队列，每遍历完一层结点，二叉树的高度就增加1。

1. 利用层次遍历

int getDepth(TreeNode *root){
	if (root == NULL)
		return 0;

	queue qu;
	TreeNode *cur = root;
	qu.push(cur);  //根节点先入队
	int depth = 0;

	while (!qu.empty()){
		int n = qu.size();  
		//获取当前队列中含有元素的个数：即，该层结点个数
		for (int i = 0; i < n; i++){
			cur = qu.front();
			qu.pop();
			if (cur->left != NULL){
				qu.push(cur->left);
			}
			if (cur->right != NULL){
				qu.push(cur->right);
			}
		}
		depth++;  //每一层的结点访问完之后，depth加1
	}
	return depth;
}

2. 利用子问题求解

int getDepth2(TreeNode *root){
	if (root == NULL)
		return 0;
	return getDepth(root->left) > getDepth(root->right) ? 
	getDepth(root->left) + 1 : getDepth(root->right) + 1;
}