LeetCode 力扣官方题解 | 590. N 叉树的后序遍历
题目描述
难易度：简单
示例 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, 104] 内 0 <= Node.val <= 104 n 叉树的高度小于或等于 1000
方法一：递归
思路
递归思路比较简单，N 叉树的前序遍历与二叉树的后序遍历的思路和方法基本一致，可以参考「145. 二叉树的后序遍历」的方法，每次递归时，先递归访问每个孩子节点，然后再访问根节点即可。
代码
Java
class Solution {public List<Integer> postorder(Node root) {List<Integer> res = new ArrayList<>();helper(root, res);return res;}public void helper(Node root, List<Integer> res) {if (root == null) {return;}for (Node ch : root.children) {helper(ch, res);}res.add(root.val);}}
C++
class Solution {public:void helper(const Node* root, vector<int> & res) {if (root == nullptr) {return;}for (auto & ch : root->children) {helper(ch, res);}res.emplace_back(root->val);}vector<int> postorder(Node* root) {vector<int> res;helper(root, res);return res;}};
C#
public class Solution {public IList<int> Postorder(Node root) {IList<int> res = new List<int>();Helper(root, res);return res;}public void Helper(Node root, IList<int> res) {if (root == null) {return;}foreach (Node ch in root.children) {Helper(ch, res);}res.Add(root.val);}}
C
#define MAX_NODE_SIZE 10000void helper(const struct Node* root, int* res, int* pos) {if (NULL == root) {return;}for (int i = 0; i < root->numChildren; i++) {helper(root->children[i], res, pos);}res[(*pos)++] = root->val;}int* postorder(struct Node* root, int* returnSize) {int * res = (int *)malloc(sizeof(int) * MAX_NODE_SIZE);int pos = 0;helper(root, res, &pos);*returnSize = pos;return res;}
JavaScript
var postorder = function(root) {const res = [];helper(root, res);return res;}const helper = (root, res) => {if (root == null) {return;}for (const ch of root.children) {helper(ch, res);}res.push(root.val);};
Python3
class Solution:def postorder(self, root: 'Node') -> List[int]:ans = []def dfs(node: 'Node'):if node is None:returnfor ch in node.children:dfs(ch)ans.append(node.val)dfs(root)return ans
Golang
func postorder(root *Node) (ans []int) {var dfs func(*Node)dfs = func(node *Node) {if node == nil {return}for _, ch := range node.Children {dfs(ch)}ans = append(ans, node.Val)}dfs(root)return}
时间复杂度：O(m)，其中 m 为 N 叉树的节点。每个节点恰好被遍历一次。 空间复杂度：O(m)，递归过程中需要调用栈的开销，平均情况下为 O(log m)，最坏情况下树的深度为 m−1，需要的空间为 O(m−1)，因此空间复杂度为 O(m)。
方法二：迭代
思路
每次入栈时都将当前。节点的 u 的第一个子节点压入栈中，直到当前节点为空节点为止。
每次查看栈顶元素 p，如果节点 p 的子节点已经全部访问过，则记录当前节点的值，并将节点 p 的从栈中弹出，并从哈希表中移除，表示该以该节点的子树已经全部遍历过；如果当前节点 p 的子节点还有未遍历的，则将当前节点的 p 的下一个未访问的节点压入到栈中，重复上述的入栈操作。
代码
Java
class Solution {public List<Integer> postorder(Node root) {List<Integer> res = new ArrayList<Integer>();if (root == null) {return res;}Map<Node, Integer> map = new HashMap<Node, Integer>();Deque<Node> stack = new ArrayDeque<Node>();Node node = root;while (!stack.isEmpty() || node != null) {while (node != null) {stack.push(node);List<Node> children = node.children;if (children != null && children.size() > 0) {map.put(node, 0);node = children.get(0);} else {node = null;}}node = stack.peek();int index = map.getOrDefault(node, -1) + 1;List<Node> children = node.children;if (children != null && children.size() > index) {map.put(node, index);node = children.get(index);} else {res.add(node.val);stack.pop();map.remove(node);node = null;}}return res;}}
C++
class Solution {public:vector<int> postorder(Node* root) {vector<int> res;if (root == nullptr) {return res;}unordered_map<Node *, int> cnt;stack<Node *> st;Node * node = root;while (!st.empty() || node != nullptr) {while (node != nullptr) {st.emplace(node);if (node->children.size() > 0) {cnt[node] = 0;node = node->children[0];} else {node = nullptr;}}node = st.top();int index = cnt.count(node) ? (cnt[node] + 1) : 0;if (index < node->children.size()) {cnt[node] = index;node = node->children[index];} else {res.emplace_back(node->val);st.pop();cnt.erase(node);node = nullptr;}}return res;}};
C#
public class Solution {public IList<int> Postorder(Node root) {IList<int> res = new List<int>();if (root == null) {return res;}Dictionary<Node, int> dictionary = new Dictionary<Node, int>();Stack<Node> stack = new Stack<Node>();Node node = root;while (stack.Count > 0 || node != null) {while (node != null) {stack.Push(node);IList<Node> childrenList = node.children;if (childrenList != null && childrenList.Count > 0) {dictionary.Add(node, 0);node = childrenList[0];} else {node = null;}}node = stack.Peek();int index = (dictionary.ContainsKey(node) ? dictionary[node] : -1) + 1;IList<Node> children = node.children;if (children != null && children.Count > index) {dictionary[node] = index;node = children[index];} else {res.Add(node.val);stack.Pop();dictionary.Remove(node);node = null;}}return res;}}
C
#define MAX_NODE_SIZE 10000typedef struct {void * key;int val;UT_hash_handle hh;} HashItem;void freeHash(HashItem ** obj) {HashItem * curr = NULL, * next = NULL;HASH_ITER(hh, *obj, curr, next) {HASH_DEL(*obj, curr);free(curr);}}int* postorder(struct Node* root, int* returnSize) {if (NULL == root) {*returnSize = 0;return NULL;}int * res = (int *)malloc(sizeof(int) * MAX_NODE_SIZE);struct Node ** stack = (struct Node **)malloc(sizeof(struct Node *) * MAX_NODE_SIZE);int pos = 0, top = 0;struct Node * node = root;HashItem * cnt = NULL;HashItem * pEntry = NULL;while (top != 0 || node != NULL) {while (node != NULL) {stack[top++] = node;if (node->numChildren > 0) {pEntry = (HashItem *)malloc(sizeof(HashItem));pEntry->key = node;pEntry->val = 0;HASH_ADD_PTR(cnt, key, pEntry);node = node->children[0];} else {node = NULL;}}node = stack[top - 1];int index = 0;HASH_FIND_PTR(cnt, &node, pEntry);if (pEntry != NULL) {index = pEntry->val + 1;}if (index < node->numChildren) {pEntry->val++;node = node->children[index];} else {top--;res[pos++] = node->val;if (pEntry != NULL) {HASH_DEL(cnt, pEntry);}node = NULL;}}free(stack);freeHash(&cnt);*returnSize = pos;return res;}
JavaScript
var postorder = function(root) {const res = [];if (root == null) {return res;}const map = new Map();const stack = [];let node = root;while (stack.length || node) {while (node) {stack.push(node);const children = node.children;if (children && children.length > 0) {map.set(node, 0);node = children[0];} else {node = null;}}node = stack[stack.length - 1];const index = (map.get(node) || 0) + 1;const children = node.children;if (children && children.length > index) {map.set(node, index);node = children[index];} else {res.push(node.val);stack.pop();map.delete(node);node = null;}}return res;};
Python3
class Solution:def postorder(self, root: 'Node') -> List[int]:if root is None:return []ans = []st = []nextIndex = defaultdict(int)node = rootwhile st or node:while node:st.append(node)if not node.children:breaknextIndex[node] = 1node = node.children[0]node = st[-1]i = nextIndex[node]if i < len(node.children):nextIndex[node] = i + 1node = node.children[i]else:ans.append(node.val)st.pop()del nextIndex[node]node = Nonereturn ans
Golang
func postorder(root *Node) (ans []int) {if root == nil {return}st := []*Node{}nextIndex := map[*Node]int{}node := rootfor len(st) > 0 || node != nil {for node != nil {st = append(st, node)if len(node.Children) == 0 {break}nextIndex[node] = 1node = node.Children[0]}node = st[len(st)-1]i := nextIndex[node]if i < len(node.Children) {nextIndex[node] = i + 1node = node.Children[i]} else {ans = append(ans, node.Val)st = st[:len(st)-1]delete(nextIndex, node)node = nil}}return}
时间复杂度：O(m)，其中 m 为 N 叉树的节点。每个节点恰好被访问一次。 空间复杂度：O(m)，其中 m 为 N 叉树的节点。如果 N 叉树的深度为 1 则此时栈和哈希表的空间为 O(1)，如果 N 叉树的深度为 m−1 则此时栈和哈希表的空间为 O(m−1)，平均情况下栈和哈希表的空间为 O(logm)，因此空间复杂度为 O(m)。
方法三：迭代优化
思路
Java
class Solution {public List<Integer> postorder(Node root) {List<Integer> res = new ArrayList<>();if (root == null) {return res;}Deque<Node> stack = new ArrayDeque<Node>();Set<Node> visited = new HashSet<Node>();stack.push(root);while (!stack.isEmpty()) {Node node = stack.peek();/* 如果当前节点为叶子节点或者当前节点的子节点已经遍历过 */if (node.children.size() == 0 || visited.contains(node)) {stack.pop();res.add(node.val);continue;}for (int i = node.children.size() - 1; i >= 0; --i) {stack.push(node.children.get(i));}visited.add(node);}return res;}}
C++
class Solution {public:vector<int> postorder(Node* root) {vector<int> res;if (root == nullptr) {return res;}stack<Node *> st;unordered_set<Node *> visited;st.emplace(root);while (!st.empty()) {Node * node = st.top();/* 如果当前节点为叶子节点或者当前节点的子节点已经遍历过 */if (node->children.size() == 0 || visited.count(node)) {res.emplace_back(node->val);st.pop();continue;}for (auto it = node->children.rbegin(); it != node->children.rend(); it++) {st.emplace(*it);}visited.emplace(node);}return res;}};
C#
public class Solution {public IList<int> Postorder(Node root) {IList<int> res = new List<int>();if (root == null) {return res;}Stack<Node> stack = new Stack<Node>();ISet<Node> visited = new HashSet<Node>();stack.Push(root);while (stack.Count > 0) {Node node = stack.Peek();/* 如果当前节点为叶子节点或者当前节点的子节点已经遍历过 */if (node.children.Count == 0 || visited.Contains(node)) {stack.Pop();res.Add(node.val);continue;}for (int i = node.children.Count - 1; i >= 0; i--) {stack.Push(node.children[i]);}visited.Add(node);}return res;}}
C
#define MAX_NODE_SIZE 10000typedef struct {void * key;UT_hash_handle hh;} HashItem;void freeHash(HashItem ** obj) {HashItem * curr = NULL, * next = NULL;HASH_ITER(hh, *obj, curr, next) {HASH_DEL(*obj, curr);free(curr);}}int* postorder(struct Node* root, int* returnSize) {if (NULL == root) {*returnSize = 0;return NULL;}int * res = (int *)malloc(sizeof(int) * MAX_NODE_SIZE);struct Node ** stack = (struct Node **)malloc(sizeof(struct Node *) * MAX_NODE_SIZE);int pos = 0, top = 0;stack[top++] = root;HashItem * visited = NULL;HashItem * pEntry = NULL;while (top != 0) {struct Node * node = stack[top - 1];pEntry = NULL;HASH_FIND_PTR(visited, &node, pEntry);/* 如果当前节点为叶子节点或者当前节点的子节点已经遍历过 */if (node->numChildren == 0 || NULL != pEntry) {res[pos++] = node->val;top--;continue;}for (int i = node->numChildren - 1; i >= 0; i--) {stack[top++] = node->children[i];}pEntry = (HashItem *)malloc(sizeof(HashItem));pEntry->key = node;HASH_ADD_PTR(visited, key, pEntry);}free(stack);*returnSize = pos;return res;}
JavaScript
var postorder = function(root) {const res = [];if (root == null) {return res;}const stack = [];const visited = new Set();stack.push(root);while (stack.length) {const node = stack[stack.length - 1];/* 如果当前节点为叶子节点或者当前节点的子节点已经遍历过 */if (node.children.length === 0 || visited.has(node)) {stack.pop();res.push(node.val);continue;}for (let i = node.children.length - 1; i >= 0; --i) {stack.push(node.children[i]);}visited.add(node);}return res;};
Python3
class Solution:def postorder(self, root: 'Node') -> List[int]:if root is None:return []ans = []st = [root]vis = set()while st:node = st[-1]# 如果当前节点为叶子节点或者当前节点的子节点已经遍历过if len(node.children) == 0 or node in vis:ans.append(node.val)st.pop()continuest.extend(reversed(node.children))vis.add(node)return ans
Golang
func postorder(root *Node) (ans []int) {if root == nil {return}st := []*Node{root}vis := map[*Node]bool{}for len(st) > 0 {node := st[len(st)-1]// 如果当前节点为叶子节点或者当前节点的子节点已经遍历过if len(node.Children) == 0 || vis[node] {ans = append(ans, node.Val)st = st[:len(st)-1]continue}for i := len(node.Children) - 1; i >= 0; i-- {st = append(st, node.Children[i])}vis[node] = true}return}
时间复杂度：O(m)，其中 m 为 N 叉树的节点。每个节点恰好被访问一次。 空间复杂度：O(m)，其中 m 为 N 叉树的节点。哈希表的空间为 O(m)，栈的空间与树的深度相同，栈的空间最大为 O(m−1)，因此空间复杂度为 O(m)。
方法四：利用前序遍历反转
思路
｛u,v1,children(v1),v2,children(v2),v3,children(v3)｝
后序遍历结果为:
｛children(v1),v1,children(v2),v2,children(v3),v3,u｝
其中 children(vk) 表示以 vk 为根节点的子树的遍历结果（不包括 vk）。仔细观察可以知道，将前序遍历中子树的访问顺序改为从右向左可以得到如下访问顺序：
｛u,v3,children(v3),v2,children(v2),v1,children(v1)｝
将上述的结果进行反转，得到:
｛children(v1),v1,children(v2),v2,children(v3),v3,u｝
代码
Java
class Solution {public List<Integer> postorder(Node root) {List<Integer> res = new ArrayList<>();if (root == null) {return res;}Deque<Node> stack = new ArrayDeque<Node>();stack.push(root);while (!stack.isEmpty()) {Node node = stack.pop();res.add(node.val);for (Node item : node.children) {stack.push(item);}}Collections.reverse(res);return res;}}
C++
class Solution {public:vector<int> postorder(Node* root) {vector<int> res;if (root == nullptr) {return res;}stack<Node *> st;st.emplace(root);while (!st.empty()) {Node * node = st.top();st.pop();res.emplace_back(node->val);for (auto &item : node->children) {st.emplace(item);}}reverse(res.begin(), res.end());return res;}};
C#
public class Solution {public IList<int> Postorder(Node root) {IList<int> res = new List<int>();if (root == null) {return res;}Stack<Node> stack = new Stack<Node>();stack.Push(root);while (stack.Count > 0) {Node node = stack.Pop();res.Add(node.val);foreach (Node item in node.children) {stack.Push(item);}}((List<int>) res).Reverse();return res;}}
C
#define MAX_NODE_SIZE 10000int* postorder(struct Node* root, int* returnSize) {if (NULL == root) {*returnSize = 0;return NULL;}int * res = (int *)malloc(sizeof(int) * MAX_NODE_SIZE);struct Node ** stack = (struct Node **)malloc(sizeof(struct Node *) * MAX_NODE_SIZE);int pos = 0, top = 0;stack[top++] = root;while (top != 0) {struct Node * node = stack[--top];res[pos++] = node->val;for (int i = 0; i < node->numChildren; i++) {stack[top++] = node->children[i];}}free(stack);for (int l = 0, r = pos - 1; l < r; l++, r--) {int tmp = res[l];res[l] = res[r];res[r] = tmp;}*returnSize = pos;return res;}
JavaScript
var postorder = function(root) {const res = [];if (root == null) {return res;}const stack = [];stack.push(root);while (stack.length) {const node = stack.pop();res.push(node.val);for (const item of node.children) {stack.push(item);}}res.reverse();return res;};
Python3
class Solution:def postorder(self, root: 'Node') -> List[int]:if root is None:return []ans = []st = [root]while st:node = st.pop()ans.append(node.val)st.extend(node.children)ans.reverse()return ans
Golang
func postorder(root *Node) (ans []int) {if root == nil {return}st := []*Node{root}for len(st) > 0 {node := st[len(st)-1]st = st[:len(st)-1]ans = append(ans, node.Val)st = append(st, node.Children...)}for i, n := 0, len(ans); i < n/2; i++ {ans[i], ans[n-1-i] = ans[n-1-i], ans[i]}return}
时间复杂度：时间复杂度：O(m)，其中 m 为 N 叉树的节点。每个节点恰好被访问一次。 空间复杂度：O(m)，其中 m 为 N 叉树的节点。如果 N 叉树的深度为 1 则此时栈的空间为 O(1)，如果 N 叉树的深度为 1 则此时栈的空间为 O(m−1)，平均情况下栈的空间为 O(logm)，因此空间复杂度为 O(m)。 BY /
本文作者：力扣
编辑&版式：Vikki 声明：本文归“力扣”版权所有，如需转载请联系。
微信扫码关注该文公众号作者
戳这里提交新闻线索和高质量文章给我们。
来源: qq
点击查看作者最近其他文章