Maximum Depth of Binary Tree

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
/*递归dfs
class Solution {
public:
    int maxDepth(TreeNode* root) {
        return dfs(root);
    }
    int dfs(TreeNode* root){
        if(root==NULL)
            return 0;
        else
            return max(dfs(root->left),dfs(root->right))+1;
    }
};
*/

/*栈dfs
class Solution{
public:
    int maxDepth(TreeNode* root){
        return dfs(root);
    }
    int dfs(TreeNode* root){
        stack<pair<TreeNode*,int>> s;
        int current_path=0;
        int max_depth=0;
        if(root!=NULL){
            s.push(make_pair(root,1));
        }
        while(!s.empty()){
            pair<TreeNode*,int> cur;
            cur=s.top();
            s.pop();
            root=cur.first;
            current_path=cur.second;
            if(current_path>max_depth)
                max_depth=current_path;
            if(root->left)
                s.push(make_pair(root->left,current_path+1));
            if(root->right)
                s.push(make_pair(root->right,current_path+1));
        }
        return max_depth;
    }
};
*/
//*队列BFS
class Solution{
public:
    int maxDepth(TreeNode* root){
        queue<TreeNode*> q;
        int max_depth=0;
        if(root!=NULL)
            q.push(root);
        while(!q.empty()){
            //当前q的size就是层次遍历时本层次的节点数；
            int width=q.size();
            while(width--){
                root=q.front();
                q.pop();
                if(root->left)
                    q.push(root->left);
                if(root->right)
                    q.push(root->right);
            }
            max_depth++;  
        }
        return max_depth;
    }
};