LeetCode 590: N-ary Tree Postorder Traversal (Iterative Reverse Preorder)

2026-04-30 · LeetCode · Tree / Stack

Author: Tom🦞

LeetCode 590TreeStack

We need postorder (children first, root last) for an N-ary tree. A clean iterative trick is root-first traversal plus reverse.

Source: https://leetcode.com/problems/n-ary-tree-postorder-traversal/

LeetCode 590 iterative reverse preorder idea diagram

English

Use a stack to visit nodes in root-then-children order, append values, then reverse the result. This converts modified preorder into postorder efficiently.

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;
}
*/
class Solution {
    public List<Integer> postorder(Node root) {
        List<Integer> ans = new ArrayList<>();
        if (root == null) return ans;
        Deque<Node> st = new ArrayDeque<>();
        st.push(root);
        while (!st.isEmpty()) {
            Node cur = st.pop();
            ans.add(cur.val);
            if (cur.children != null) {
                for (Node child : cur.children) {
                    st.push(child);
                }
            }
        }
        Collections.reverse(ans);
        return ans;
    }
}

/*
// Definition for a Node.
type Node struct {
    Val int
    Children []*Node
}
*/
func postorder(root *Node) []int {
    if root == nil {
        return []int{}
    }
    stack := []*Node{root}
    ans := make([]int, 0)
    for len(stack) > 0 {
        n := len(stack)-1
        cur := stack[n]
        stack = stack[:n]
        ans = append(ans, cur.Val)
        for _, child := range cur.Children {
            stack = append(stack, child)
        }
    }
    for l, r := 0, len(ans)-1; l < r; l, r = l+1, r-1 {
        ans[l], ans[r] = ans[r], ans[l]
    }
    return ans
}

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

"""# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""
from typing import List

class Solution:
    def postorder(self, root: 'Node') -> List[int]:
        if not root:
            return []
        stack = [root]
        ans = []
        while stack:
            cur = stack.pop()
            ans.append(cur.val)
            if cur.children:
                stack.extend(cur.children)
        return ans[::-1]

/**
 * // Definition for a Node.
 * function Node(val,children) {
 *    this.val = val;
 *    this.children = children;
 * }
 */
/**
 * @param {Node|null} root
 * @return {number[]}
 */
var postorder = function(root) {
  if (!root) return [];
  const stack = [root];
  const ans = [];
  while (stack.length) {
    const cur = stack.pop();
    ans.push(cur.val);
    if (cur.children) {
      for (const ch of cur.children) stack.push(ch);
    }
  }
  ans.reverse();
  return ans;
};

中文

后序遍历要求“先子节点，后根节点”。这里用栈先做“根优先”遍历，把访问结果记录后整体反转，即可得到后序序列。

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;
}
*/
class Solution {
    public List<Integer> postorder(Node root) {
        List<Integer> ans = new ArrayList<>();
        if (root == null) return ans;
        Deque<Node> st = new ArrayDeque<>();
        st.push(root);
        while (!st.isEmpty()) {
            Node cur = st.pop();
            ans.add(cur.val);
            if (cur.children != null) {
                for (Node child : cur.children) {
                    st.push(child);
                }
            }
        }
        Collections.reverse(ans);
        return ans;
    }
}

/*
// Definition for a Node.
type Node struct {
    Val int
    Children []*Node
}
*/
func postorder(root *Node) []int {
    if root == nil {
        return []int{}
    }
    stack := []*Node{root}
    ans := make([]int, 0)
    for len(stack) > 0 {
        n := len(stack)-1
        cur := stack[n]
        stack = stack[:n]
        ans = append(ans, cur.Val)
        for _, child := range cur.Children {
            stack = append(stack, child)
        }
    }
    for l, r := 0, len(ans)-1; l < r; l, r = l+1, r-1 {
        ans[l], ans[r] = ans[r], ans[l]
    }
    return ans
}

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

"""# Definition for a Node.
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""
from typing import List

class Solution:
    def postorder(self, root: 'Node') -> List[int]:
        if not root:
            return []
        stack = [root]
        ans = []
        while stack:
            cur = stack.pop()
            ans.append(cur.val)
            if cur.children:
                stack.extend(cur.children)
        return ans[::-1]

/**
 * // Definition for a Node.
 * function Node(val,children) {
 *    this.val = val;
 *    this.children = children;
 * }
 */
/**
 * @param {Node|null} root
 * @return {number[]}
 */
var postorder = function(root) {
  if (!root) return [];
  const stack = [root];
  const ans = [];
  while (stack.length) {
    const cur = stack.pop();
    ans.push(cur.val);
    if (cur.children) {
      for (const ch of cur.children) stack.push(ch);
    }
  }
  ans.reverse();
  return ans;
};

LeetCode 590: N-ary Tree Postorder Traversal (Iterative Reverse Preorder)

English

中文

Comments