题目

590. N 叉树的后序遍历

分析

我们之前有做过LeetCode的 145. 二叉树的后序遍历，其实对于 N 叉树来说和二叉树的思路是一模一样的。
二叉树的后序遍历是【左 右 根】
N叉树的后序遍历顺序是【孩子 根】，你可以把二叉树的【左 右 根】想象成【孩子 根】，因为左右就是孩子。

PS：【145. 二叉树的后序遍历】 的讲解博文链接：LeetCode.145. 二叉树的后序遍历

代码

先看一下二叉树后序遍历的代码：

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();func(root,res);return res;}void func(TreeNode cur,List<Integer> res) {if(cur == null) return ;// 先遍历左子树func(cur.left,res);// 再遍历右子树func(cur.right,res);// 最后记录根节点res.add(cur.val);}
}

只需要改动一点就是N叉树的后序遍历代码，如下：

/*
// Definition for a Node.
class Node {public int val;public List<Node> children;public Node() {}public Node(int _val) {val = _val;}public Node(int _val, List<Node> _children) {val = _val;children = _children;}
};
*/class Solution {public List<Integer> postorder(Node root) {List<Integer> res = new ArrayList<>();if(root == null) return res;pos(root,res);return res;}void pos(Node cur,List<Integer> res) {if(cur == null) return ;// 先记录孩子for(Node node : cur.children) {pos(node,res);}// 在记录当前节点res.add(cur.val);}
}