[LeetCode] 589. N-ary Tree Preorder Traversal

Given an n-ary tree, return the preorder traversal of its nodes' values.

For example, given a 3-ary tree:

Return its preorder traversal as: [1,3,5,6,2,4].

这个题目思路就是跟LeetCode questions conlusion_InOrder, PreOrder, PostOrder traversal类似, recursive 和iterable都可以.

04/17/2019 update: 加第三种方法，利用divide and conquer

1. Recursively

class Solution:

    def nary_Preorder(self, root):

        def helper(root):

            if not root: return

            ans.append(root.val)

            for each in root.children:

                helper(each)

        ans = []

        helper(root)

        return ans

2. Iterable

class Solution:

    def nary_preOrder(self, root):

        if not root: return []

        stack, ans = [root], []

        while stack:

            node = stack.pop()

            ans.append(node.val)

            for each in node.children[::-1]:

                stack.append(each)

        return ans

3. Divide and conquer

# Divide and conquer

class Solution:

    def preOrder(self, root):

        if not root: return []

        temp = []

        for each in root.children:

            temp += self.preOrder(each)

        return [root.val] + temp

巴特西

[LeetCode] 589. N-ary Tree Preorder Traversal_Easy

最新文章

热门文章