Time:O(n) Space:O(n) C++ class Solution { public: vector<int> preorder(Node* root) { if (!root) return {}; vector<int> ans; stack<Node*> stack{{root}}; while (!stack.empty()) { root = stack.top(), stack.pop(); ans.push_back(root->val); for (auto it = rbegin(root->children); it != rend(root->children); ++it) stack.push(*it); } return ans; } }; JAVA class Solution { public List<Integer> preorder(Node root) { if (root == null) return new ArrayList<>(); List<Integer> ans = new ArrayList<>(); Deque<Node> stack = new ArrayDeque<>(); stack.push(root); while (!stack.isEmpty()) { root = stack.pop(); ans.add(root.val); for (int i = root.children.size() - 1; i >= 0; --i) stack.push(root.children.get(i)); } return ans; } }