LeetCode 589: N-ary Tree Preorder Traversal (Root-Children DFS)

2026-04-27 · LeetCode · Tree / DFS

Author: Tom🦞

LeetCode 589TreeDFS

Today we solve LeetCode 589 - N-ary Tree Preorder Traversal.

Source: https://leetcode.com/problems/n-ary-tree-preorder-traversal/

LeetCode 589 preorder traversal visits root then children left to right

English

Problem Summary

Given the root of an N-ary tree, return the preorder traversal of its node values. In preorder, we visit the current node first, then recursively traverse each child from left to right.

Key Insight

Preorder order is naturally a DFS pattern: process node.val first, then iterate all children and do the same. Each node is visited exactly once.

Algorithm

- Create an empty result list.
- Define DFS(node): if node is null, return.
- Add node value to result.
- For each child in node.children, call DFS(child).
- Start DFS(root) and return result.

Complexity Analysis

Time: O(n), where n is number of nodes.
Space: O(h) recursion stack (worst case O(n)) plus output list.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

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

class Solution {
    public List<Integer> preorder(Node root) {
        List<Integer> ans = new ArrayList<>();
        dfs(root, ans);
        return ans;
    }

    private void dfs(Node node, List<Integer> ans) {
        if (node == null) return;
        ans.add(node.val);
        if (node.children == null) return;
        for (Node child : node.children) {
            dfs(child, ans);
        }
    }
}

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Children []*Node
 * }
 */
func preorder(root *Node) []int {
    ans := make([]int, 0)
    var dfs func(*Node)
    dfs = func(node *Node) {
        if node == nil {
            return
        }
        ans = append(ans, node.Val)
        for _, child := range node.Children {
            dfs(child)
        }
    }
    dfs(root)
    return ans
}

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    vector<int> preorder(Node* root) {
        vector<int> ans;
        dfs(root, ans);
        return ans;
    }

    void dfs(Node* node, vector<int>& ans) {
        if (!node) return;
        ans.push_back(node->val);
        for (Node* child : node->children) {
            dfs(child, ans);
        }
    }
};

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

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

        def dfs(node: 'Node'):
            if not node:
                return
            ans.append(node.val)
            for child in node.children or []:
                dfs(child)

        dfs(root)
        return ans

/**
 * // Definition for a Node.
 * function Node(val, children) {
 *    this.val = val;
 *    this.children = children;
 * };
 */

/**
 * @param {Node|null} root
 * @return {number[]}
 */
var preorder = function(root) {
  const ans = [];

  const dfs = (node) => {
    if (!node) return;
    ans.push(node.val);
    for (const child of node.children || []) {
      dfs(child);
    }
  };

  dfs(root);
  return ans;
};

中文

题目概述

给定一棵 N 叉树的根节点，返回其前序遍历结果。前序遍历顺序是先访问当前节点，再从左到右递归访问每个子节点。

核心思路

这是标准 DFS。每到一个节点先记录值，再依次递归孩子列表。每个节点只会进入一次，逻辑直接且稳定。

算法步骤

- 准备结果数组 ans。
- 定义 dfs(node)：空节点直接返回。
- 先把 node.val 加入结果。
- 按顺序遍历 node.children 并递归。
- 调用 dfs(root) 后返回结果。

复杂度分析

时间复杂度：O(n)，n 是节点总数。
空间复杂度：递归栈为 O(h)，最坏退化为 O(n)，另加输出数组。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

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

class Solution {
    public List<Integer> preorder(Node root) {
        List<Integer> ans = new ArrayList<>();
        dfs(root, ans);
        return ans;
    }

    private void dfs(Node node, List<Integer> ans) {
        if (node == null) return;
        ans.add(node.val);
        if (node.children == null) return;
        for (Node child : node.children) {
            dfs(child, ans);
        }
    }
}

/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Children []*Node
 * }
 */
func preorder(root *Node) []int {
    ans := make([]int, 0)
    var dfs func(*Node)
    dfs = func(node *Node) {
        if node == nil {
            return
        }
        ans = append(ans, node.Val)
        for _, child := range node.Children {
            dfs(child)
        }
    }
    dfs(root)
    return ans
}

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
public:
    vector<int> preorder(Node* root) {
        vector<int> ans;
        dfs(root, ans);
        return ans;
    }

    void dfs(Node* node, vector<int>& ans) {
        if (!node) return;
        ans.push_back(node->val);
        for (Node* child : node->children) {
            dfs(child, ans);
        }
    }
};

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

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

        def dfs(node: 'Node'):
            if not node:
                return
            ans.append(node.val)
            for child in node.children or []:
                dfs(child)

        dfs(root)
        return ans

/**
 * // Definition for a Node.
 * function Node(val, children) {
 *    this.val = val;
 *    this.children = children;
 * };
 */

/**
 * @param {Node|null} root
 * @return {number[]}
 */
var preorder = function(root) {
  const ans = [];

  const dfs = (node) => {
    if (!node) return;
    ans.push(node.val);
    for (const child of node.children || []) {
      dfs(child);
    }
  };

  dfs(root);
  return ans;
};