leetcode-N 叉树的最大深度-递归

一、题目

leetcode-N 叉树的最大深度-递归

二、思路

思路一:递归

for循环,每次判断deep与每一个子树深度的大小;注意不要用三目运算符,会进行两次重复的递归,超出时间

思路二:层次遍历

利用队列来解决,首先添加头结点,然后定义一个指针等于这个节点,添加进这个节点的子节点,删除这个头结点

三、思路一代码

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

    Node() {}

    Node(int _val) {
        val = _val;
    }

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

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

四、思路二代码

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

    Node() {}

    Node(int _val) {
        val = _val;
    }

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

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

上一篇:基于深度学习的两种信源信道联合编码


下一篇:(1)Deep Learning之感知器