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

题解一： 深度优先
题解思路： 使用深度优先遍历所有根到叶节点的深度，树的深度等于左子树的深度与右子树深度的最大值+1.
图示：

递归分析：
递归边界： 当root的为空，返回0
递归过程： 计算root左子树深度和root右子树深度

复杂度分析：
时间复杂度：O(N)： 每个节点需要遍历一次
空间复杂度：O(N) ： 最坏情况树退化为链表
实现如下:

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(!root) return 0;  //递归边界
         return max(maxDepth(root->left),maxDepth(root->right))+1;  //计算左子树和右子树深度取大者最后+1 = 树的深度
    }
};

题解二： 层次遍历
题解思路：使用层次遍历直接求二叉树的深度
分析：
1.自定义结构体node_deep表示每个节点所在的深度，其属性为TreeNode* node, int depth;
2.使用队列用于保存每层的节点
3.如果队列为空，就返回ans。
图示：

复杂度分析：
时间复杂度：O(N) :每个节点需要遍历一次
空间复杂度：O(N) : 最坏情况树为完全平衡树，队列同时存储着N/2个节点。
实现如下:

class Solution {
public:
    /**
     *
     * @param root TreeNode类
     * @return int整型
     */
    struct node_deep{
        TreeNode* node;  //节点
        int depth;   //该节点所在的层
        node_deep(TreeNode* t = NULL,int d = 0):node(t),depth(d){};
    };

    int maxDepth(TreeNode* root) {
        // write code here
        if(!root) return 0;  //root为NULL，返回0
        int ans = 0;  //树的深度
        queue<node_deep*> q;
        node_deep* head = new node_deep(root,1);
        q.push(head);  //将根节点入队
        while(!q.empty()){
            node_deep * tmp = q.front(); q.pop();
            ans = tmp->depth;  //ans = 当前所在层深度
           //下一层的节点入队且depth+1
            if(tmp->node->left) {
                node_deep * left_node = new node_deep(tmp->node->left,tmp->depth+1); 
                q.push(left_node);
            }
            if(tmp->node->right){
                node_deep * right_node = new node_deep(tmp->node->right,tmp->depth+1);
                q.push(right_node);
            }
        }
        return ans;
    }
};

相关题目：
二叉树层序遍历