【Leetcode】559. Maximum Depth of N-ary Tree

求N-叉树的最大深度

方法1 有helper函数的递归

要注意递归停止的条件不是root==None，而是root 没有孩子

class Solution1(object):
    def maxDepth(self, root):
        """
        :type root: Node
        :rtype: int
        """
        if root == None:
            return 0
        self.res = 0
        self.DFS(root, 1)
        return  self.res

    def DFS(self, root, level):
        self.res = max(self.res, level)
        for child in root.children:
            self.DFS(child, level+1)

方法2 没有helper函数的递归

class Solution2(object):
    def maxDepth(self, root):
        """
        :type root: Node
        :rtype: int
        """
        if root == None:
            return 0
        if root.children == None:
            return 1
        res  = 0
        for child in root.children:
            res = max(self.maxDepth(child),res)
        return res +1

方法3 深搜非递归

class Solution3(object):
    def maxDepth(self, root):
        """
        :type root: Node
        :rtype: int
        """
        if root == None:
            return 0
        stack = [[root,1]]
        res = 0
        while(len(stack)):
            node,depth = stack.pop()
            if node.children == [] or node.children == None:
                res = max(res, depth)
            else:
                for child in node.children:
                    stack.append([child, depth+1])
        return res

方法4 层次遍历

class Solution4(object):
    def maxDepth(self, root):
        """
        :type root: Node
        :rtype: int
        """
        if root == None:
            return 0
        res = 0
        from collections import deque
        queue = deque()
        queue.append(root)
        while(len(queue)):
            res +=1
            length = len(queue)
            for i in range(length):
                node = queue.popleft()
                for child in node.children:
                    queue.append(child)
        return res