LeetCode 559. N叉树的最大深度

Michael阿明

发布于 2020-07-13 14:30:34

2230

发布于 2020-07-13 14:30:34

文章被收录于专栏：Michael阿明学习之路Michael阿明学习之路

1. 题目

给定一个 N 叉树，找到其最大深度。

最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。

2. 解题

2.1 递归

class Solution {
public:
    int maxDepth(Node* root) {
    	if(root == NULL)
    		return 0;
    	int childDep = 0;
    	for(int i = 0; i < root->children.size(); ++i)
    	{
    		childDep = max(childDep, maxDepth(root->children[i]));
    	}
		return childDep+1;
    }
};

2.2 按层queue遍历

class Solution {
public:
    int maxDepth(Node* root) {
    	if(root == NULL)
    		return 0;
    	int deep = 0;
    	queue<Node*> q;
    	Node *tp;
    	q.push(root);
    	int n, i;
    	while(!q.empty())
    	{
    		++deep;
    		n = q.size();
    		while(n--)
    		{
    			tp = q.front();
    			for(i = 0; i < tp->children.size(); ++i)
    				q.push(tp->children[i]);
    			q.pop();
    		}
    	}
    	return deep;
    }
};

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2019-09-17 ，如有侵权请联系 cloudcommunity@tencent.com 删除

queue