LeetCode 589. N 叉树的前序遍历

Categories:

题目描述
思路分析
1. 解法一：迭代栈（推荐）
相似题目

题目描述

✅ 589. N 叉树的前序遍历

思路分析

解法一：迭代栈（推荐）

核心思路：

前序遍历顺序为：根 -> 从左到右的子节点。

用栈保存节点，先压入根，每次弹出后逆序压入子节点，保证左子树先访问。

复杂度分析：

时间复杂度：O(n)，其中 n 表示节点数。

空间复杂度：O(h)，其中 h 表示树高，最坏情况下 O(n)。

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

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

        Deque<Node> stack = new ArrayDeque<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            Node cur = stack.pop();
            res.add(cur.val);

            List<Node> children = cur.children;
            if (children == null) {
                continue;
            }

            for (int i = children.size() - 1; i >= 0; i--) {
                stack.push(children.get(i));
            }
        }

        return res;
    }
}

func preorder(root *Node) []int {
	res := make([]int, 0)
	if root == nil {
		return res
	}

	stack := []*Node{root}
	for len(stack) > 0 {
		cur := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		res = append(res, cur.Val)

		children := cur.Children
		for i := len(children) - 1; i >= 0; i-- {
			stack = append(stack, children[i])
		}
	}

	return res
}

相似题目

题目	难度	考察点
144. 二叉树的前序遍历	简单	前序遍历
590. N 叉树的后序遍历	简单	栈
429. N 叉树的层序遍历	中等	BFS
102. 二叉树的层序遍历	中等	BFS
94. 二叉树的中序遍历	简单	DFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/42301082