leetcode刷题-559. Maximum Depth of N-ary Tree

题目： https://leetcode.com/problems/maximum-depth-of-n-ary-tree/description/

n-ary-tree的数据结果表示

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

    Node() {}

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

　　DFS算法：迭代

int maxDepth(Node* root) {
        if (root == NULL) return 0;
        int max = 0, n = root->children.size();
        for (int i = 0; i<n; i++)
        {
            int temp=maxDepth(root->children[i]);
            if (temp>max)
                max = temp;
            //max=std::max(max,maxDepth(root->children[i]));
        }
        return max + 1;
    }

BFS算法：队列

int maxDepth(Node* root) {
        if (root == NULL) return 0;
        int res=0;
        queue<Node*> Q;
        Q.push(root);
        while(!Q.empty())
        {
            res++;
            int n=Q.size();
            for(int i=0;i<n;i++)
            {
                Node* t=Q.front();
                
                for(int j=0;j<t->children.size();j++)
                    Q.push(t->children[j]);
                Q.pop();
            }
        }
        return res;
    }

leetcode刷题-559. Maximum Depth of N-ary Tree

相关推荐