考察知识点：二叉树的遍历

题目描述

输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

题解

解法一：树的层序遍历

分析

借助队列 q 对树结点进行层序遍历，借助队列 hq 存储当前结点深度
根结点入队列 q ，深度 1 入队列 hq，当队列 q 不为空时，做：

  1. 出队 q 最前元素 T 和当前树深度 h；
  2. 如果 T 有左子树，左子树入队 q，当前 h + 1 入队 hq；
  3. 如果 T 有右子树，右子树入队 q，当前 h + 1 入队 hq；
  4. 更新最大深度 Max
代码
/* 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)
    {
    	// 如果为空树，返回树深度为 0
		if(!pRoot)
			return 0;
       // 定义队列 q，用到 STL，头文件需要加 include<queue>
        queue<TreeNode*> q;
		queue<int> hq;
		// 定义临时树结点 T 和树深度 h
		TreeNode* T; 
		int h = 1;
		// 定义深度
		int Max = 0;
		// 入队根节点与其深度
		q.push(pRoot);
		hq.push(h);
		// 当队列 q 不为空，做循环
		while(!q.empty()){
			// 获取当前树结点和深度
			T = q.front();q.pop();
			int Th = hq.front();hq.pop();
			// 如果有左子树
			if(T->left){
				q.push(T->left);
				hq.push(Th+1);
			}
			// 如果有右子树
			if(T->right){
				q.push(T->right);
				hq.push(Th+1);
			}
			// 更新最大深度
			Max = max(Th,Max);
		}
		return Max;
    }
};

解法二：递归

分析

由树的定义可知，每多一层儿子结点，深度 + 1，即当前深度 = 子结点深度 + 1
要寻找树的最大深度，即寻找左右儿子结点中最大的深度 + 1… 如此递归下去，如果为空树，返回 0

代码
/* 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)
    {
    	// 如果为空树，返回树深度为 0
        if(!pRoot)
            return 0;
        // 返回左子树最大深度
        int MaxLeft = TreeDepth(pRoot->left);
        // 返回右子树最大深度
        int MaxRight = TreeDepth(pRoot->right);
        // 返回当前结点最大深度
        return max(MaxLeft,MaxRight) + 1;
    }
};