題目

難度：★★☆☆☆
類型：樹

給定一個 N 叉樹，返回其節(jié)點值的前序遍歷。

例如，給定一個 3叉樹 :

N叉樹

返回其前序遍歷: [1,3,5,6,2,4]。

說明: 遞歸法很簡單，你可以使用迭代法完成此題嗎?

解答

方案1：遞歸

class Solution:
    def preorder(self, root):

        def pre_order(node, l):
            """
            N叉樹的前序遍歷
            :param node: 輸入結(jié)點
            :param l: 結(jié)果列表
            :return:
            """
            if node:                            # 如果輸入結(jié)點不為空
                l.append(node.val)              # 添加結(jié)點值到結(jié)果列表
                for child in node.children:     # 對每一棵子樹做前序遍歷
                    pre_order(child, l)

        res = []
        pre_order(root, res)
        return res

上述方法的緊湊寫法：

class Solution:
    def preorder(self, root):        
        return [root.val]+sum([self.preorder(i) for i in root.children], []) if root else []

方案2：迭代

class Solution:
    def preorder(self, root):
        if root is None:
            return []
        stack = [root]
        res = []
        while len(stack):
            node = stack.pop()
            res.append(node.val)
            temp = []
            for i in node.children:
                temp.append(i)
            if len(temp):
                temp.reverse()
                stack.extend(temp)
        return res

如有疑問或建議，歡迎評論區(qū)留言~