559. Maximum Depth of N-ary Tree

發表於 | 分類於

problem

solution

dfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int maxDepth(Node* root) {
        
        // dfs
        if(!root) return 0;
        // for binary tree
        // return 1+max(maxDepth(root->left), maxDepth(root->right));
        
        // n-ary tree
        int depth=1, mx = 0;
        for(Node *t:root->children){
            mx = max(mx, maxDepth(t));
        }
        return 1+mx;
    }
};

bfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int maxDepth(Node* root) {
        if(!root) return 0;
        queue<Node*> q({root});
        int depth = 0;
        while(!q.empty()){
            int size = q.size();
            for(int i=0;i<size;++i){
                Node *  p =q.front(); 
                q.pop();
                for(Node *t:p->children) q.push(t);
            }
            depth++;
        }
        return depth;
    }
};