Easy

题目描述

给定一个 N 叉树，返回其节点值的前序遍历。

N 叉树输入按层序遍历序列化表示，每组子节点都由 null 值分隔（参见示例）。

示例 1：

输入：root = [1,null,3,2,4,null,5,6]
输出：[1,3,5,6,2,4]

示例 2：

输入：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]
输出：[1,2,3,6,7,11,14,4,8,12,5,9,13,10]

约束条件：

  • 树中节点数目在范围 [0, 10^4] 内
  • 0 <= Node.val <= 10^4
  • N 叉树的高度小于或等于 1000

进阶： 递归解法很简单，你可以通过迭代算法完成吗？

解题思路

解题思路

N 叉树的前序遍历与二叉树的前序遍历类似，遍历顺序为：根节点 → 所有子节点。

方法一：递归解法（推荐）

递归是最直观的解法。对于每个节点：

  1. 先访问当前节点，将其值加入结果
  2. 然后递归遍历所有子节点

方法二：迭代解法

使用栈来模拟递归过程：

  1. 将根节点入栈
  2. 当栈不为空时，弹出栈顶节点并访问
  3. 将该节点的所有子节点从右到左入栈（保证左子节点先被访问）

注意：由于栈是后进先出的特性，我们需要从右到左将子节点入栈，这样左边的子节点会先被弹出访问。

两种方法的时间复杂度都是 O(n)，空间复杂度在最坏情况下都是 O(h)，其中 h 是树的高度。递归解法更简洁直观，迭代解法避免了可能的栈溢出问题。

代码实现

/*
// 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> result;
        if (!root) return result;
        
        stack<Node*> stk;
        stk.push(root);
        
        while (!stk.empty()) {
            Node* node = stk.top();
            stk.pop();
            result.push_back(node->val);
            
            // 从右到左入栈，保证左子节点先被访问
            for (int i = node->children.size() - 1; i >= 0; i--) {
                stk.push(node->children[i]);
            }
        }
        
        return result;
    }
};

"""
# Definition for a Node.
class Node:
    def __init__(self, val: Optional[int] = None, children: Optional[List['Node']] = None):
        self.val = val
        self.children = children
"""

class Solution:
    def preorder(self, root: 'Node') -> List[int]:
        if not root:
            return []
        
        result = []
        stack = [root]
        
        while stack:
            node = stack.pop()
            result.append(node.val)
            
            # 从右到左入栈，保证左子节点先被访问
            for child in reversed(node.children):
                stack.append(child)
        
        return result

/*
// Definition for a Node.
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) {
        IList<int> result = new List<int>();
        if (root == null) return result;
        
        Stack<Node> stack = new Stack<Node>();
        stack.Push(root);
        
        while (stack.Count > 0) {
            Node node = stack.Pop();
            result.Add(node.val);
            
            // 从右到左入栈，保证左子节点先被访问
            for (int i = node.children.Count - 1; i >= 0; i--) {
                stack.Push(node.children[i]);
            }
        }
        
        return result;
    }
}

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

/**
 * @param {_Node|null} root
 * @return {number[]}
 */
var preorder = function(root) {
    if (!root) return [];
    
    const result = [];
    const stack = [root];
    
    while (stack.length > 0) {
        const node = stack.pop();
        result.push(node.val);
        
        // 从右到左入栈，保证左子节点先被访问
        for (let i = node.children.length - 1; i >= 0; i--) {
            stack.push(node.children[i]);
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型递归解法迭代解法
时间复杂度O(n)O(n)
空间复杂度O(h)O(h)

其中 n 是树中节点的总数，h 是树的高度。在最坏情况下（完全不平衡的树），h = n，空间复杂度为 O(n)。

相关题目