题解 | 二叉树的深度

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
    int TreeDepth(TreeNode* pRoot) {
		if(!pRoot)	return 0;
		//这是一个语言的逻辑，因为没有直接在函数内部修改或者参数修改而显得不直观，
		//有时候人们会奇怪于为什么它能够成功改变，似乎子树是不变的
		//其实这是没有抓住递归的本质是对当前位置进行修改，而不是在参数里进行修改
		//我们要克服这种心理，接受直观描述并用代码复现
		//这道题的直观描述就是比子树中最大的加一，就这样递归就行。
		return max(TreeDepth(pRoot->left), TreeDepth(pRoot->right))+1;
    }
};

方法一：

这个是官方题解的方案，更简洁明了，下一个是我写的代码，基本一样的思路但是长很多，在官方代码中我注释了我没有采用这个方案的原因。

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

	int curDepth=-1;
	void vDepth(TreeNode* node, int dep){
		if(!node) return;
		if(curDepth<dep) curDepth = dep;
		if(node->left) vDepth(node->left, dep+1);
		if(node->right) vDepth(node->right, dep+1);
	}
    int TreeDepth(TreeNode* pRoot) {
		if(!pRoot) return 0;
		vDepth(pRoot, 1);
		return curDepth;
    }
};

也是递归，但是我相当于先序遍历，官方相当于后序遍历。我习惯在能处理结果时就得到结果，而不是等到最后处理。

/*
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) return 0;
		int ans = 0;
		queue<TreeNode*> q;
		q.push(pRoot);
		while(!q.empty()){
			int len = q.size();
			for(int i = 0; i < len; ++i){
				TreeNode* temp = q.front();
				q.pop();
				if(temp->left) q.push(temp->left);
				if(temp->right)	q.push(temp->right);
			}
			++ans;
		}
		return ans;
    }
};

方法二：层次遍历

相对于直观的深度遍历（每次到更深的地方+1或者回更浅层的时候+1)，层次遍历可能没有那么让人能够第一时间想到。

但树的深度正是一层一层的，所以我们也可以用层次遍历记录层数。一般来说不常记录层数，大多层次遍历是为了解决递归时栈深度太深的问题。

一个巧妙的记录层数方法就是（双层循环）用内部循环消耗完每一层的节点，然后再进行下一次外部迭代，

此时下一层的节点已经全部入队且没有其他层的元素，就可以记录队列中的元素数量作为内部循环的执行次数。

如此反复直到队列为空。

以上三个代码的时间和空间复杂度都是O(n)。