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 10000
void 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:
return
for 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 10000
typedef 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 = root
while st or node:
while node:
st.append(node)
if not node.children:
break
nextIndex[node] = 1
node = node.children[0]
node = st[-1]
i = nextIndex[node]
if i < len(node.children):
nextIndex[node] = i + 1
node = node.children[i]
else:
ans.append(node.val)
st.pop()
del nextIndex[node]
node = None
return ans
Golang
func postorder(root *Node) (ans []int) {
if root == nil {
return
}
st := []*Node{}
nextIndex := map[*Node]int{}
node := root
for len(st) > 0 || node != nil {
for node != nil {
st = append(st, node)
if len(node.Children) == 0 {
break
}
nextIndex[node] = 1
node = node.Children[0]
}
node = st[len(st)-1]
i := nextIndex[node]
if i < len(node.Children) {
nextIndex[node] = i + 1
node = 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 10000
typedef 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()
continue
st.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 10000
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;
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 声明:本文归“力扣”版权所有,如需转载请联系。
微信扫码关注该文公众号作者