LeetCode 589: N-ary Tree Preorder Traversal Solution
Master LeetCode problem 589 (N-ary Tree Preorder Traversal), a easy challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.
589. N-ary Tree Preorder Traversal
Problem Explanation
Explanation:
To perform a preorder traversal on an n-ary tree iteratively, we can use a stack to keep track of the nodes to be visited. We start by pushing the root node onto the stack. Then, while the stack is not empty, we pop a node, add its value to the result list, and push its children onto the stack in reverse order. By pushing the children in reverse order, we ensure that the first child is processed first.
Algorithm:
- Initialize an empty stack and result list.
- Push the root node onto the stack.
- While the stack is not empty:
- Pop a node from the stack.
- Add the node's value to the result list.
- Push the node's children onto the stack in reverse order.
- Return the result list.
Time Complexity: O(n) where n is the number of nodes in the tree. Space Complexity: O(n) where n is the number of nodes in the tree.
:
Solution Code
class Solution {
public List<Integer> preorder(Node root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
Stack<Node> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
Node node = stack.pop();
result.add(node.val);
for (int i = node.children.size() - 1; i >= 0; i--) {
stack.push(node.children.get(i));
}
}
return result;
}
}Try It Yourself
Loading code editor...
Related LeetCode Problems
Frequently Asked Questions
How to solve LeetCode 589 (N-ary Tree Preorder Traversal)?
This page provides optimized solutions for LeetCode problem 589 (N-ary Tree Preorder Traversal) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.
What is the time complexity of LeetCode 589 (N-ary Tree Preorder Traversal)?
The time complexity for LeetCode 589 (N-ary Tree Preorder Traversal) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.
Can I run code for LeetCode 589 on DevExCode?
Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 589 in Java, C++, or Python.