Preorder traversal of Li Kou 589:n fork tree

2022 year 03 month 10 Japan Try to make a daily question

subject

Given a n  The root node of the fork tree  root , return Of its node value The former sequence traversal .

n Fork tree In the input sequence traversal serialization representation , Each group of child nodes consists of null values null Separate （ See example ）.

Example 1：

 Input ：root = [1,null,3,2,4,null,5,6]
 Output ：[1,3,5,6,2,4]

Example 2：

 Input ：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
 Output ：[1,2,3,6,7,11,14,4,8,12,5,9,13,10]

 

Tips ：

• The total number of nodes is in the range  [0, 104] Inside
• 0 <= Node.val <= 104
• n The height of the fork tree is less than or equal to 1000

 

Advanced ： Recursion is very simple , Can you use the iteration method to complete this problem ?

Related Topics

• Stack
• Trees
• Depth-first search

Personal solution

java Code ：

class Solution {
    
    List<Integer> list = new ArrayList<>();
    public List<Integer> preorder(Node root) {
    
        dfs(root);
        return list;
    }
    void dfs(Node root) {
    
        if (root == null) {
    
            return;
        }
        list.add(root.val);
        for (Node node : root.children) {
    
            dfs(node);
        }
    }
}

python3 Code ：

""" # Definition for a Node. class Node: def __init__(self, val=None, children=None): self.val = val self.children = children """
from typing import List


class Solution:
    def preorder(self, root: 'Node') -> List[int]:
        result = []

        def dfs(node):
            if node:
                result.append(node.val)
                for child in node.children:
                    dfs(child)

        dfs(root)
        return result