Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

【每日一题】- 2019-09-27 - 559. N叉树的最大深度 #189

Closed
azl397985856 opened this issue Sep 27, 2019 · 4 comments
Closed

【每日一题】- 2019-09-27 - 559. N叉树的最大深度 #189

azl397985856 opened this issue Sep 27, 2019 · 4 comments

Comments

@azl397985856
Copy link
Owner

@azl397985856 azl397985856 commented Sep 27, 2019

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

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

例如,给定一个 3叉树 :

image

我们应返回其最大深度,3。

说明:

树的深度不会超过 1000。
树的节点总不会超过 5000。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/maximum-depth-of-n-ary-tree
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

@azl397985856

This comment has been minimized.

Copy link
Owner Author

@azl397985856 azl397985856 commented Sep 27, 2019

可以尝试使用递归和非递归两种方式解决

@aleafboat

This comment has been minimized.

Copy link
Contributor

@aleafboat aleafboat commented Sep 30, 2019

C++ 递归

class Solution {
public:
  int maxDepth(Node *root) {
    if (NULL == root) {
      return 0;
    }
    if (root->children.size() == 0) {
      return 1; //提升4ms,不需要做for循环判断
    }

    int depth = 0;
    for (int i = 0; i < root->children.size(); i++) {
      depth =
          max(depth,
              maxDepth(root->children[i])); //选择最大的一个,这里没有+1这动作
    }

    return depth + 1;
  }
};

c++ 非递归

class Solution_DFS {
public:
  int maxDepth(Node *root) {
    if (NULL == root) {
      return 0;
    }
    std::stack<pair<Node*, int>> mystack;    //深度遍历特点
    mystack.push(pair<Node*, int>(root, 1)); //从上到下传递深度
    int max_depth = 0; //统计从root节点到leaf节点之间最大距离

    while (!mystack.empty()) {
      Node *tempNode = mystack.top().first;
      int depth = mystack.top().second; //出栈 
      mystack.pop();

      //从左到右遍历,空节点不入栈
      for (Node *it : tempNode->children) {
        if (it) {
          mystack.push(pair<Node *, int>(it, depth + 1));
        }
      }
      //if (tempNode->children.size() ==0 ) { 添加 size 判断增加20ms的时间
        max_depth = max(max_depth, depth);
      //}
     
    }
    return max_depth;
  }
};
@lyltj2010

This comment has been minimized.

Copy link

@lyltj2010 lyltj2010 commented Nov 18, 2019

Java递归版本

    public int maxDepth(Node root) {
        if (root == null) return 0;
        int max = 0;
        for (Node node : root.children) {
            max = Math.max(max, maxDepth(node));
        }
        return 1 + max;
    }
@stale

This comment has been minimized.

Copy link

@stale stale bot commented Jan 17, 2020

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.

@stale stale bot added the stale label Jan 17, 2020
@stale stale bot closed this Jan 24, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
3 participants
You can’t perform that action at this time.