广州公司网站制作,湛江网站搜索优化,中铁建设集团门户网登录入口官网,新浪微博网页版qq登录入口559. N 叉树的最大深度
给定一个 N 叉树#xff0c;找到其最大深度。
最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
N 叉树输入按层序遍历序列化表示#xff0c;每组子节点由空值分隔#xff08;请参见示例#xff09;。 示例 1#xff1a; 输入#…559. N 叉树的最大深度
给定一个 N 叉树找到其最大深度。
最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
N 叉树输入按层序遍历序列化表示每组子节点由空值分隔请参见示例。 示例 1 输入root [1,null,3,2,4,null,5,6] 输出3 示例 2 输入root [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14] 输出5 提示
树的深度不会超过 1000 。树的节点数目位于 [0, 104] 之间。
解题思路
使用递归每个递归函数返回的是以输入参数root为根节点的子树所具有的最大深度。每次递归计算所有的子节点得出子节点中的最大深度然后加上当前节点的深度一返回给上层调用。
代码
/*
// Definition for a Node.
class Node {
public:int val;vectorNode* children;Node() {}Node(int _val) {val _val;}Node(int _val, vectorNode* _children) {val _val;children _children;}
};
*/class Solution {
public:int maxDepth(Node* root) {if (root nullptr) return 0;int res(0);for (auto c:root-children)resmax(maxDepth(c),res);return res1;}
};时间复杂度O(n)O(n)O(n)其中 n 为 N 叉树节点的个数。每个节点在递归中只被遍历一次。
空间复杂度O(height)O(\textit{height})O(height)其中$ \textit{height}$ 表示 N 叉树的高度。递归函数需要栈空间而栈空间取决于递归的深度因此空间复杂度等价于 N 叉树的高度。
解题思路
利用队列实现对N叉树的层序遍历并且记录下访问到的最大的层数就是最大深度
代码
/*
// Definition for a Node.
class Node {
public:int val;vectorNode* children;Node() {}Node(int _val) {val _val;}Node(int _val, vectorNode* _children) {val _val;children _children;}
};
*/class Solution {
public:int maxDepth(Node *root) {if (root nullptr) return 0;int res(0);queueNode * q;q.push(root);while (!q.empty()) {int s q.size();for (int i 0; i s; i) {Node *cur q.front();q.pop();for (auto c:cur-children) {if (c ! nullptr)q.push(c);}}res;}return res;}
};
