[알고리즘문제] 릿코드 Maximum Depth of N-ary Tree

leetcode.com/problems/maximum-depth-of-n-ary-tree/

Maximum Depth of N-ary Tree - LeetCode

 

DFS로 푸는 문제이다.

2진트리가 주어지면

최대 depth를 return

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}
    ~Node() { children.clear(); }

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};

//Node의 가장 최대 Depth를 구하기
class Solution {
private:
    vector<Node*> v;
    priority_queue<int> last;
public:
    int maxDepth(Node* root) {
        if (root == nullptr) return 0;
        return dfs(root, 1);
    }
    int dfs(Node* root, int max) {
        Node* tmp;
        if (!last.empty()) {
            if (last.top() < max) {
                last.push(max);
            }
        }
        else {
            last.push(max);
        }
        for (int i = 0; i < root->children.size(); i++) {
            tmp = root->children[i];
            dfs(tmp, max + 1);
        }

        return last.top();
    }
    ~Solution() {
        while (!last.empty()) {
            last.pop();
        }
    }
};

argument로 2진트리와, depth값을 준다.

depth를 증가시키며 priority_queue(우선순위 q)에 넣는다. 

priority_queue보다 depth가 더 크면 depth를 push

dfs 종료 시 priority_queue의 top(가장 큰 값)을 return 한다.