Share a LeetCode topic each day

Make progress together for 5 minutes a day

LeetCode Preorder traversal of N fork tree, address: leetcode-cn.com/problems/n-…

The tree node class

class TreeNode(object) :
    def __init__(self, val, children=[]) :
        self.val = val
        self.children = children
Copy the code

Antecedent traversal of N – tree

Use recursion, still follow the “left and right” traversal principle

def preorder(self, root) :
    print(root.val, end="")
    for node in root.children:
        self.preorder(node)
Copy the code

Doesn’t it look super simple, but it doesn’t fit the LeetCode question

You need to place the result in an array, so you need to initialize a list to store it

Let’s recode it

def preorder(self, root) :
    # print(root.val, end=" ")
    # for node in root.children:
    # self.preorder(node)

    res = []
    def dfs(root) :
        if not root:
            return
        res.append(root.val)
        for node in root.children:
            dfs(node)
    dfs(root)
    return res
Copy the code

The res is initialized ahead of time, and then the assignment is performed during traversal

The complete code

Directly executable

# -*- coding:utf-8 -*-
# !/usr/bin/env python

# tree node class
class Node(object) :
    def __init__(self, val=None, children=[]) :
        self.val = val
        self.children = children

class Solution(object) :
    def preorder(self, root) :
        # print(root.val, end=" ")
        # for node in root.children:
        # self.preorder(node)

        res = []
        def dfs(root) :
            if not root:
                return
            res.append(root.val)
            for node in root.children:
                dfs(node)
        dfs(root)
        return res


if __name__ == "__main__":
    Create a new node
    root = Node('A')
    node_B = Node('B')
    node_C = Node('C')
    node_D = Node('D')
    node_E = Node('E')
    node_F = Node('F')
    node_G = Node('G')
    node_H = Node('H')
    node_I = Node('I')
    # Build a trigeminal tree
    # A
    # / | \
    # B C D
    # / | \ \
    # E F G H I
    root.children = [node_B, node_C, node_D]
    node_B.children = [node_E, node_F, node_G]
    node_D.children = [node_H, node_I]

    s = Solution()
    print(s.preorder(root))
Copy the code

Have fun ღ(´ · ᴗ · ‘)