【剑指offr--C/C++】JZ55 二叉树的深度

一、题目

求二叉树深度两个思路：递归、层次遍历。

二、递归思路及代码
每一个节点的深度都=max{左子树深度，右子树深度}+1。所以可以使用递归

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
#include <queue>
class Solution {
public:
    int TreeDepth(TreeNode* pRoot) {
        if(pRoot==NULL) return 0;
        int leftData=TreeDepth(pRoot->left);//左树深度
        int rightData=TreeDepth(pRoot->right);//右树深度
        int rootData=leftData>rightData?leftData:rightData;//取较大值
        return rootData+1;//加上自己这一层
    
    }
};

三、层次遍历思路及代码
//层次遍历：用队列辅助
//先将root放进去，记录当前这一层的节点个数，
//然后依次取出这一层节点并将其左右子节点放进去
//层数+1
//重复上述步骤直到节点遍历完成

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
#include <queue>
class Solution {
public:
    int TreeDepth(TreeNode* pRoot) {

		if(pRoot==NULL) return 0;
		queue<TreeNode*> nodeQue;
		int dep=0;
		TreeNode* root=pRoot;
	    nodeQue.push(root);
		while(!nodeQue.empty()){
			int n=nodeQue.size();
			for(int i=0;i<n;i++){
				TreeNode *node=nodeQue.front();
				if(node->left){
                  nodeQue.push(node->left);
				}
				if(node->right){
                  nodeQue.push(node->right);
				}
				
				nodeQue.pop();
			}
			dep+=1;
		}
		return dep;
    
    }
};