0590. N-ary Tree Postorder Traversal =================================== 题目信息 -------- :题号: 0590 :难度: Easy :主题: N 叉树、后序遍历、孩子顺序、值序列 :原题: `LeetCode 0590 `_ :重点: 先按 children 从左到右遍历全部子树、最后访问当前节点、空树返回空数组 题目重述 -------- 给定一棵 N 叉树的根节点 ``root``,返回它的后序遍历节点值序列。 后序遍历按照节点 ``children`` 数组中的顺序,从左到右完整遍历每棵子树,最后才访问当前节点。兄弟节点顺序不能改变;若树为空,返回空数组。 自建示例 -------- 根节点最后访问: .. code-block:: text 输入:根 1 的孩子为 [2,3,4],3 的孩子为 [5,6] 输出:[2,5,6,3,4,1] 解释:先完成 2、3、4 三棵子树的后序遍历,最后访问根节点 1。 只有根节点: .. code-block:: text 输入:root = [7] 输出:[7] 解释:没有子树,直接在最后访问根节点。 先递归孩子再记录当前节点 ------------------------ 后序遍历的递归结构直接对应定义:按 children 从左到右调用每棵子树,所有孩子完成后才把当前节点值追加到结果。空节点不产生值。 C++ 实现 -------- .. code-block:: cpp class Solution { std::vector result; void visit(Node* node) { if (node == nullptr) return; for (Node* child : node->children) visit(child); result.push_back(node->val); } public: std::vector postorder(Node* root) { result.clear(); visit(root); return result; } }; 代码分析 -------- 递归返回前才记录节点,保证所有孩子及其后代先出现且顺序不变;每个节点访问一次,时间复杂度为 ``O(n)``,递归栈空间为 ``O(h)``。