当前位置：首页 > article >正文

LeetCode题练习与总结：N 叉树的后序遍历--590

article 2025/1/30 18:07:41

一、题目描述

给定一个 n 叉树的根节点 root ，返回其节点值的 后序遍历 。

n 叉树在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。

示例 1：

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

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

提示：

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

二、解题思路

初始化结果列表和栈：
- 创建一个ArrayList实例result用于存放遍历的结果。
- 创建一个Stack实例stack用于在迭代过程中存储节点。
检查根节点：
- 如果根节点root为null，直接返回空的result列表，因为空树没有节点可以遍历。
将根节点入栈：
- 将根节点root压入栈中，以便开始遍历过程。
迭代处理栈中的节点：
- 进入一个while循环，只要栈stack不为空，就继续执行循环体。
- 在每次循环中，从栈中弹出一个节点，并将其赋值给current变量。
添加当前节点值到结果列表：
- 将current节点的值添加到result列表中。注意，这里我们添加的是当前节点的值，而不是子节点的值。
将子节点逆序入栈：
- 遍历当前节点的所有子节点，并将它们逆序压入栈中。之所以要逆序入栈，是因为栈是后进先出的数据结构，逆序入栈可以保证子节点在父节点之前被处理，这样当我们添加到结果列表时，父节点会出现在子节点之后。
反转结果列表：
- 由于我们是在每次处理节点时，先将父节点的值添加到结果列表中，然后再处理子节点，所以最终得到的结果列表是根节点在子节点之前。为了得到正确的后序遍历结果（子节点在根节点之前），我们需要将结果列表result反转。
返回结果：
- 最后，返回反转后的结果列表result，这就是n叉树的后序遍历结果。

三、具体代码

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

class Solution {
    public List<Integer> postorder(Node root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            Node current = stack.pop();
            result.add(current.val);
            // 将子节点逆序入栈，这样出栈时就是正序
            for (Node child : current.children) {
                stack.push(child);
            }
        }
        // 反转结果列表，因为我们是先添加根节点再添加子节点
        Collections.reverse(result);
        return result;
    }
}

四、时间复杂度和空间复杂度

1. 时间复杂度

初始化结果列表和栈：
- 初始化result列表和stack栈的时间复杂度是O(1)。
检查根节点：
- 检查根节点是否为null的时间复杂度是O(1)。
将根节点入栈：
- 将根节点入栈的时间复杂度是O(1)。
迭代处理栈中的节点：
- 这个过程涉及到一个while循环，循环次数等于树中节点的总数n。
- 在每次循环中，我们需要执行的操作包括：弹出一个节点（O(1)）、添加节点值到结果列表（O(1)）、将所有子节点逆序入栈（最坏情况下是O(n)，因为一个节点可能有n个子节点）。
反转结果列表：
- 反转结果列表的时间复杂度是O(n)，因为需要遍历整个列表。

综合以上步骤，总的时间复杂度是O(n^2)，其中n是树中节点的总数。这是因为对于每个节点，我们可能需要将其所有子节点入栈，这是一个与节点数量相关的操作，而我们需要对每个节点都执行这样的操作。

2. 空间复杂度

结果列表：
- result列表存储所有节点的值，因此空间复杂度是O(n)，其中n是树中节点的总数。
栈：
- stack栈在最坏情况下可能需要存储所有的节点，因此空间复杂度也是O(n)。
递归调用栈：
- 虽然代码中使用了迭代而非递归，但在迭代过程中，栈的使用模拟了递归调用栈的行为。在最坏情况下，栈可能需要存储所有的节点，因此空间复杂度是O(n)。

综合以上分析，总的空间复杂度是O(n)，其中n是树中节点的总数。

五、总结知识点

类定义：
- class Solution：定义了一个名为Solution的类。
成员方法：
- public List<Integer> postorder(Node root)：定义了一个公共方法postorder，它接受一个Node类型的参数root，并返回一个List<Integer>类型的列表。
数据结构：
- List<Integer>：泛型列表，用于存储整数类型的元素。
- Stack<Node>：栈数据结构，用于存储Node类型的元素，遵循后进先出（LIFO）的原则。
条件语句：
- if (root == null)：条件判断，用于检查传入的根节点是否为null。
循环结构：
- while (!stack.isEmpty())：while循环，用于在栈不为空的情况下重复执行代码块。
栈操作：
- stack.push(root)：将元素压入栈顶。
- Node current = stack.pop()：从栈顶弹出一个元素。
列表操作：
- result.add(current.val)：将元素添加到列表的末尾。
- Collections.reverse(result)：反转列表中的元素顺序。
迭代器：
- for (Node child : current.children)：增强型for循环，用于遍历Node类型的children列表。
方法返回值：
- return result;：返回方法的结果。
泛型：
- List<Integer>和Stack<Node>都是泛型类型的实例，它们分别指定了列表和栈中元素的类型。
接口和实现：
- Node类和List、Stack接口都是Java集合框架的一部分，这里使用的是接口的实现。