給定一個(gè)二叉樹(shù)，找出其最大深度。

二叉樹(shù)的深度為根節(jié)點(diǎn)到最遠(yuǎn)葉子節(jié)點(diǎn)的最長(zhǎng)路徑上的節(jié)點(diǎn)數(shù)。

說(shuō)明: 葉子節(jié)點(diǎn)是指沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)。

示例：
給定二叉樹(shù) [3,9,20,null,null,15,7]，

image.png

返回它的最大深度 3 。

思路1(dfs)

int maxDepth(struct TreeNode* root) {
    if(root==NULL){
        return 0;
    }
    int leftDepth=maxDepth(root->left)+1;
    int rightDepth=maxDepth(root->right)+1;
    
    if(leftDepth>rightDepth){
        return leftDepth;
    }else{
        return rightDepth;
    }
}

思路2(bfs)

采用隊(duì)列，把一層節(jié)點(diǎn)都加進(jìn)隊(duì)列，之后一個(gè)個(gè)將隊(duì)頭刪除，并且每刪除一個(gè)隊(duì)頭，把它的左右孩子節(jié)點(diǎn)加進(jìn)來(lái)

class Solution {
public:
    int maxDepth(TreeNode* root) {
         if(root == NULL){
             return 0;
         }
                 
        queue<TreeNode*> q;
        q.push(root);
        int count=0;
        while(!q.empty()){
            count++;
            for(int i=0,n=q.size();i<n;++i){
                TreeNode* p=q.front();
                q.pop();
                if(p->left!=NULL){
                    q.push(p->left);
                }
                if(p->right!=NULL){
                    q.push(p->right);
                }
            }
        }
        return count;
    }
};