Easy

题目描述

给定一个 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

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

解题思路

解题思路

N 叉树的后序遍历是指按照"左子树 → 右子树 → 根节点"的顺序访问节点。对于 N 叉树，即按照"所有子树 → 根节点"的顺序。

方法一：递归解法

这是最直观的解法。对于每个节点，先递归遍历其所有子节点，然后访问当前节点。递归的终止条件是遇到空节点。

方法二：迭代解法（推荐）

使用栈模拟递归过程。关键思路是：

  1. 使用栈存储节点，从根节点开始
  2. 每次取出栈顶节点，将其值加入结果数组的头部
  3. 将该节点的所有子节点按顺序压入栈中
  4. 重复直到栈为空

这种方法实际上是先序遍历的变种，通过在结果数组头部插入元素，巧妙地实现了后序遍历的效果。

两种解法都是有效的，递归解法代码更简洁易懂，迭代解法更能体现对数据结构的理解，在面试中更有亮点。

代码实现

class Solution {
public:
    vector<int> postorder(Node* root) {
        vector<int> result;
        if (!root) return result;
        
        stack<Node*> st;
        st.push(root);
        
        while (!st.empty()) {
            Node* node = st.top();
            st.pop();
            result.insert(result.begin(), node->val);
            
            for (Node* child : node->children) {
                if (child) st.push(child);
            }
        }
        
        return result;
    }
};

class Solution:
    def postorder(self, root: 'Node') -> List[int]:
        if not root:
            return []
        
        result = []
        stack = [root]
        
        while stack:
            node = stack.pop()
            result.insert(0, node.val)
            
            for child in node.children:
                if child:
                    stack.append(child)
        
        return result

public class Solution {
    public IList<int> Postorder(Node root) {
        var result = new List<int>();
        if (root == null) return result;
        
        var stack = new Stack<Node>();
        stack.Push(root);
        
        while (stack.Count > 0) {
            var node = stack.Pop();
            result.Insert(0, node.val);
            
            foreach (var child in node.children) {
                if (child != null) {
                    stack.Push(child);
                }
            }
        }
        
        return result;
    }
}

var postorder = function(root) {
    if (!root) return [];
    
    const result = [];
    const stack = [root];
    
    while (stack.length > 0) {
        const node = stack.pop();
        result.unshift(node.val);
        
        for (const child of node.children) {
            if (child) {
                stack.push(child);
            }
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

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

其中 n 是树中节点的总数，h 是树的高度。递归解法的空间复杂度主要来自系统调用栈，迭代解法需要额外的栈空间存储节点。

相关题目