589. N-ary Tree Preorder Traversal

leetcode easy

#backtracking#csharp#easy#leetcode#stack#tree

Task

Дан корень N-арного дерева, верните значения его узлов в порядке предварительного (preorder) обхода.

Сериализация ввода N-арного дерева представлена в их обходе уровнями. Каждая группа детей разделена значением null (См. примеры).

Пример:

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]

C# solution

matched/original

using System.Collections.Generic;
public class Node {
    public int val;
    public IList<Node> children;
    public Node() {}
    public Node(int _val) {
        val = _val;
    }
    public Node(int _val, IList<Node> _children) {
        val = _val;
        children = _children;
    }
}
public class Solution {
    public IList<int> Preorder(Node root) {
        var output = new List<int>();
        if (root == null) return output;
        
        var stack = new Stack<Node>();
        stack.Push(root);
        
        while (stack.Count > 0) {
            var node = stack.Pop();
            output.Add(node.val);
            for (int i = node.children.Count - 1; i >= 0; i--) {
                stack.Push(node.children[i]);
            }
        }
        
        return output;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
public class Node {
    public int val;
    public IList<Node> children;
    public Node() {}
    public Node(int _val) {
        val = _val;
    }
    public Node(int _val, IList<Node> _children) {
        val = _val;
        children = _children;
    }
}
class Solution {
public:
    public vector<int> Preorder(Node root) {
        var output = new List<int>();
        if (root == null) return output;
        
        var stack = new stack<Node>();
        stack.push(root);
        
        while (stack.size() > 0) {
            var node = stack.pop();
            output.push_back(node.val);
            for (int i = node.children.size() - 1; i >= 0; i--) {
                stack.push(node.children[i]);
            }
        }
        
        return output;
    }
}

Java solution

matched/original

class Solution {
    public List<Integer> preorder(Node root) {
        LinkedList<Node> stack = new LinkedList<>();
        LinkedList<Integer> output = new LinkedList<>();
        if (root == null) {
            return output;
        }

        stack.add(root);
        while (!stack.isEmpty()) {
            Node node = stack.pollLast();
            output.add(node.val);
            Collections.reverse(node.children);
            for (Node item : node.children) {
                stack.add(item);
            }
        }
        return output;
    }
    class Node {
        public int val;
        public List<Node> children;

        public Node() {}

        public Node(int _val,List<Node> _children) {
            val = _val;
            children = _children;
        }
    }
}

JavaScript solution

matched/original

function Node(val, children) {
    this.val = val;
    this.children = children || [];
}

var preorder = function(root) {
    if (root === null) return [];
    let stack = [root];
    let output = [];
    
    while (stack.length > 0) {
        let node = stack.pop();
        output.push(node.val);
        for (let i = node.children.length - 1; i >= 0; i--) {
            stack.push(node.children[i]);
        }
    }
    
    return output;
};

Python solution

matched/original

class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children if children is not None else []

class Solution:
    def preorder(self, root: 'Node') -> List[int]:
        if not root:
            return []
        stack, output = [root], []
        
        while stack:
            node = stack.pop()
            output.append(node.val)
            stack.extend(reversed(node.children))
        
        return output\

Go solution

matched/original

type Node struct {
    Val      int
    Children []*Node
}

func preorder(root *Node) []int {
    if root == nil {
        return nil
    }
    stack := []*Node{root}
    output := []int{}
    
    for len(stack) > 0 {
        node := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        output = append(output, node.Val)
        for i := len(node.Children) - 1; i >= 0; i-- {
            stack = append(stack, node.Children[i])
        }
    }
    
    return output
}

Explanation

Algorithm

Инициализация

Создайте два списка: stack для хранения узлов и output для хранения значений узлов в порядке обхода. Добавьте корневой узел в stack.

Итеративный обход

Пока stack не пуст, извлекайте узел из stack и добавляйте его значение в output. Разверните список дочерних узлов текущего узла и добавьте их в stack.

Возврат результата

Верните список output как результат.

😎