题解 | #二叉树的最大深度#

题目：二叉树的最大深度

描述：求给定二叉树的最大深度，最大深度是指树的根结点到最远叶子结点的最长路径上结点的数量。

示例1：输入：{1,2}，返回值：2

解法一：

思路分析：二叉树的深度就是从根节点到最远子结点的距离，在此我们要考虑当二叉树为空时，其深度应该为0，如果二叉树不为空，则方法应该是分别求出左子树和右子树的深度，最后取得最大值。

实例分析：输入：{1,2,3,4,#,#,5}，返回值：3

该二叉树的模型图为：

由上图分析可知，1的左子树的左子树为4，深度为3，1的右子树的右子树为5，深度也为3，故根据判别式sub_left > sub_right ? sub_left : sub_right可得最大深度为3.

具体C++代码如下所示：

/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 * };
 */
 
class Solution {
public:
    /**
     *
     * @param root TreeNode类
     * @return int整型
     */
    int maxDepth(TreeNode* root) {
        if(root == nullptr)//特殊情况
            return 0;
        int sub_left = maxDepth(root->left);//递归判断
        int sub_right = maxDepth(root->right);
        return (sub_left > sub_right ? sub_left : sub_right) + 1;//返回最大值
    }
};

或

/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 * };
 */
 
class Solution {
public:
    /**
     *
     * @param root TreeNode类
     * @return int整型
     */
    int maxDepth(TreeNode* root) {
        // write code here
        if(root == NULL)
            return 0;
        return 1+max(maxDepth(root->left), maxDepth(root->right));//直接返回左或者右的最大值或者最小值
    }
};

因为递归遍历了每一个元素，所以其时间复杂度为O(N)，空间复杂度为O(1)。

解法二：

思路分析：二叉树的高度和深度是相反的表示，深度是从上到小数的，高度是从下到上数的。某节点的深度指的是从根节点到该节点最长简单路径的条数，高度指的是从该结点到叶子结点的最长简单路径的条数。

我们亦可以采用层序遍历加队列的方式去解决问题，首先将root放入队列当中，表示deep为1，其次进行层序遍历，遍历每一层的元素，如果元素存在，则deep + 1否则直接返回最终的结果值。

实例分析：输入：{1,2,3,4,#,#,5}，返回值：3

	

		/**
 * struct TreeNode {
 *    int val;
 *    struct TreeNode *left;
 *    struct TreeNode *right;
 * };
 */
 
class Solution {
public:
    /**
     *
     * @param root TreeNode类
     * @return int整型
     */
    int maxDepth(TreeNode* root) {
        // write code here
        if (!root)
            return 0;
        deque<treenode> q;//定义一个双端队列
        q.push_back(root);//将根结点存进去
        int deep = 0;
        while (!q.empty()) {
            ++deep;
            int num = q.size();//队列的大小，方便进行判断
            for (int i = 1; i <=num; ++i) { 
                TreeNode* p = q.front();//开头元素 
                q.pop_front();//出队列
                if (p->left)
                    q.push_back(p->left);
                if (p->right)
                    q.push_back(p->right);
            }
        }
        return deep;
    }
};</treenode>
	

同时二叉树还有如下性质：
1：在二叉树的第i层上至少有2^（i-1）个结点
2：深度为k的二叉树至多有2^(k-1)个结点
3：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1
4：具有n个结点的完全二叉树的深度是[log2n]+1（向下取整）