题目

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：
给定二叉树 [3,9,20,null,null,15,7]，

  1.     3
  2.    / \
  3.   9  20
  4.     /  \
  5.    15   7

返回它的最大深度 3 。

解题方法

BFS

通过 BFS 遍历二叉树，记录最大层数。
时间复杂度O(n)，空间复杂度O(n)
C++代码：

  1. /**
  2.  * Definition for a binary tree node.
  3.  * struct TreeNode {
  4.  *     int val;
  5.  *     TreeNode *left;
  6.  *     TreeNode *right;
  7.  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  8.  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9.  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  10.  * };
  11.  */
  12. class Solution {
  13. public:
  14.     int maxDepth(TreeNode* root) {
  15.         int depth = 0;
  16.         queue<TreeNode*> nodes;
  17.         if(root!=NULL)  nodes.push(root);
  18.         while(nodes.size()>0) {
  19.             depth++;
  20.             int size = nodes.size();
  21.             for(int i=0; i<size; i++) {
  22.                 if(nodes.front()->left)     nodes.push(nodes.front()->left);
  23.                 if(nodes.front()->right)    nodes.push(nodes.front()->right);
  24.                 nodes.pop();
  25.             }
  26.         }
  28.         return depth;
  29.     }
  30. };

DFS

通过 DFS 递归遍历二叉树，更新最大深度。
时间复杂度O(n)，空间复杂度O(height)，空间复杂度为二叉树最大深度。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void DFS(TreeNode *cur, int level, int &depth) {
        if(!cur) return;
        depth = level > depth ? level : depth;
        DFS(cur->left, level+1, depth);
        DFS(cur->right, level+1, depth);
    }

    int maxDepth(TreeNode* root) {
        int depth = 0;
        DFS(root, 1, depth);

        return depth;
    }
};